Arrays and Strings: The Foundation of Data Structures

// TypeScript - Dynamic array (grows automatically)
const arr: number[] = [1, 2, 3];
arr.push(4);  // Adds to end - usually O(1), sometimes O(n) when resizing
arr.push(5);
 
// JavaScript arrays are dynamic by default
const dynamicArr: any[] = [];
dynamicArr.push(1);
dynamicArr.push("hello");  // Can even hold mixed types
dynamicArr.push({ name: "Alice" });

# Python - Lists are dynamic arrays
arr = [1, 2, 3]
arr.append(4)  # O(1) amortized
arr.append(5)
 
# Python lists can hold mixed types
mixed_list = [1, "hello", {"name": "Alice"}]

Index:    0     1     2     3     4
Value:  [10]  [20]  [30]  [40]  [50]
Address: 100   104   108   112   116  (assuming 4 bytes per int)

Before: [10, 20, 30, 40]
Insert 5 at index 0:
        [5, 10, 20, 30, 40]
           ←←←←  All elements shifted

// TypeScript - Insert/delete operations
const arr = [10, 20, 30, 40];
 
// Insert at beginning - O(n)
arr.unshift(5);  // [5, 10, 20, 30, 40]
 
// Insert at end - O(1) amortized
arr.push(50);    // [5, 10, 20, 30, 40, 50]
 
// Delete from beginning - O(n)
arr.shift();     // [10, 20, 30, 40, 50]
 
// Delete from end - O(1)
arr.pop();       // [10, 20, 30, 40]
 
// Insert at middle - O(n)
arr.splice(2, 0, 25);  // [10, 20, 25, 30, 40]
 
// Delete from middle - O(n)
arr.splice(2, 1);      // [10, 20, 30, 40]

# Python - Insert/delete operations
arr = [10, 20, 30, 40]
 
# Insert at beginning - O(n)
arr.insert(0, 5)  # [5, 10, 20, 30, 40]
 
# Insert at end - O(1) amortized
arr.append(50)    # [5, 10, 20, 30, 40, 50]
 
# Delete from beginning - O(n)
arr.pop(0)        # [10, 20, 30, 40, 50]
 
# Delete from end - O(1)
arr.pop()         # [10, 20, 30, 40]
 
# Insert at middle - O(n)
arr.insert(2, 25) # [10, 20, 25, 30, 40]
 
# Delete from middle - O(n)
del arr[2]        # [10, 20, 30, 40]

// TypeScript - Reverse array in-place
function reverseInPlace(arr: number[]): void {
  let left = 0;
  let right = arr.length - 1;
 
  while (left < right) {
    // Swap elements
    [arr[left], arr[right]] = [arr[right], arr[left]];
    left++;
    right--;
  }
}
 
const nums = [1, 2, 3, 4, 5];
reverseInPlace(nums);
console.log(nums); // [5, 4, 3, 2, 1]

# Python - Reverse array in-place
def reverse_in_place(arr: list[int]) -> None:
    left, right = 0, len(arr) - 1
 
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1
 
nums = [1, 2, 3, 4, 5]
reverse_in_place(nums)
print(nums)  # [5, 4, 3, 2, 1]

// TypeScript - Two Sum in Sorted Array
function twoSumSorted(nums: number[], target: number): number[] {
  let left = 0;
  let right = nums.length - 1;
 
  while (left < right) {
    const sum = nums[left] + nums[right];
 
    if (sum === target) {
      return [left, right];
    } else if (sum < target) {
      left++;  // Need larger sum
    } else {
      right--; // Need smaller sum
    }
  }
 
  return [-1, -1]; // Not found
}
 
console.log(twoSumSorted([2, 7, 11, 15], 9)); // [0, 1]
console.log(twoSumSorted([1, 2, 3, 4, 6], 6)); // [1, 3]

# Python - Two Sum in Sorted Array
def two_sum_sorted(nums: list[int], target: int) -> list[int]:
    left, right = 0, len(nums) - 1
 
    while left < right:
        current_sum = nums[left] + nums[right]
 
        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
 
    return [-1, -1]
 
print(two_sum_sorted([2, 7, 11, 15], 9))  # [0, 1]

// TypeScript - Remove Duplicates from Sorted Array (in-place)
function removeDuplicates(nums: number[]): number {
  if (nums.length === 0) return 0;
 
  let slow = 0;  // Points to last unique element
 
  for (let fast = 1; fast < nums.length; fast++) {
    if (nums[fast] !== nums[slow]) {
      slow++;
      nums[slow] = nums[fast];
    }
  }
 
  return slow + 1;  // Length of unique portion
}
 
const nums = [1, 1, 2, 2, 2, 3, 4, 4];
const length = removeDuplicates(nums);
console.log(nums.slice(0, length)); // [1, 2, 3, 4]

# Python - Remove Duplicates from Sorted Array
def remove_duplicates(nums: list[int]) -> int:
    if not nums:
        return 0
 
    slow = 0
 
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
 
    return slow + 1
 
nums = [1, 1, 2, 2, 2, 3, 4, 4]
length = remove_duplicates(nums)
print(nums[:length])  # [1, 2, 3, 4]

// TypeScript - Maximum sum of k consecutive elements
function maxSumSubarray(nums: number[], k: number): number {
  if (nums.length < k) return -1;
 
  // Calculate sum of first window
  let windowSum = 0;
  for (let i = 0; i < k; i++) {
    windowSum += nums[i];
  }
 
  let maxSum = windowSum;
 
  // Slide the window
  for (let i = k; i < nums.length; i++) {
    windowSum += nums[i];      // Add new element
    windowSum -= nums[i - k];  // Remove old element
    maxSum = Math.max(maxSum, windowSum);
  }
 
  return maxSum;
}
 
console.log(maxSumSubarray([2, 1, 5, 1, 3, 2], 3)); // 9 (5+1+3)

# Python - Maximum sum of k consecutive elements
def max_sum_subarray(nums: list[int], k: int) -> int:
    if len(nums) < k:
        return -1
 
    # Calculate sum of first window
    window_sum = sum(nums[:k])
    max_sum = window_sum
 
    # Slide the window
    for i in range(k, len(nums)):
        window_sum += nums[i]      # Add new element
        window_sum -= nums[i - k]  # Remove old element
        max_sum = max(max_sum, window_sum)
 
    return max_sum
 
print(max_sum_subarray([2, 1, 5, 1, 3, 2], 3))  # 9

// TypeScript - Longest substring without repeating characters
function lengthOfLongestSubstring(s: string): number {
  const charIndex = new Map<string, number>();
  let maxLength = 0;
  let left = 0;
 
  for (let right = 0; right < s.length; right++) {
    const char = s[right];
 
    // If char was seen and is in current window
    if (charIndex.has(char) && charIndex.get(char)! >= left) {
      left = charIndex.get(char)! + 1;  // Shrink window
    }
 
    charIndex.set(char, right);
    maxLength = Math.max(maxLength, right - left + 1);
  }
 
  return maxLength;
}
 
console.log(lengthOfLongestSubstring("abcabcbb")); // 3 ("abc")
console.log(lengthOfLongestSubstring("bbbbb"));    // 1 ("b")
console.log(lengthOfLongestSubstring("pwwkew"));   // 3 ("wke")

# Python - Longest substring without repeating characters
def length_of_longest_substring(s: str) -> int:
    char_index = {}
    max_length = 0
    left = 0
 
    for right, char in enumerate(s):
        # If char was seen and is in current window
        if char in char_index and char_index[char] >= left:
            left = char_index[char] + 1  # Shrink window
 
        char_index[char] = right
        max_length = max(max_length, right - left + 1)
 
    return max_length
 
print(length_of_longest_substring("abcabcbb"))  # 3
print(length_of_longest_substring("bbbbb"))     # 1
print(length_of_longest_substring("pwwkew"))    # 3

// TypeScript/JavaScript - Strings are immutable
let s = "hello";
// s[0] = "H";  // This doesn't work!
s = "H" + s.slice(1);  // Create new string
console.log(s); // "Hello"

# Python - Strings are immutable
s = "hello"
# s[0] = "H"  # TypeError!
s = "H" + s[1:]  # Create new string
print(s)  # "Hello"
 
# For many modifications, use list then join
chars = list("hello")
chars[0] = "H"
s = "".join(chars)
print(s)  # "Hello"

// Java - Strings are immutable
String s = "hello";
// s.charAt(0) = 'H';  // Not possible!
 
// Use StringBuilder for mutations
StringBuilder sb = new StringBuilder("hello");
sb.setCharAt(0, 'H');
String result = sb.toString(); // "Hello"

// TypeScript - String operations
const s = "Hello, World!";
 
// Length
console.log(s.length); // 13
 
// Access character
console.log(s[0]);     // "H"
console.log(s.charAt(0)); // "H"
 
// Substring
console.log(s.slice(0, 5));    // "Hello"
console.log(s.substring(7));    // "World!"
 
// Search
console.log(s.indexOf("World")); // 7
console.log(s.includes("Hello")); // true
 
// Case conversion
console.log(s.toLowerCase()); // "hello, world!"
console.log(s.toUpperCase()); // "HELLO, WORLD!"
 
// Split
console.log(s.split(", ")); // ["Hello", "World!"]
 
// Trim
console.log("  hello  ".trim()); // "hello"
 
// Replace
console.log(s.replace("World", "TypeScript")); // "Hello, TypeScript!"

# Python - String operations
s = "Hello, World!"
 
# Length
print(len(s))  # 13
 
# Access character
print(s[0])    # "H"
print(s[-1])   # "!"
 
# Substring (slicing)
print(s[0:5])  # "Hello"
print(s[7:])   # "World!"
 
# Search
print(s.find("World"))  # 7
print("Hello" in s)     # True
 
# Case conversion
print(s.lower())  # "hello, world!"
print(s.upper())  # "HELLO, WORLD!"
 
# Split
print(s.split(", "))  # ["Hello", "World!"]
 
# Strip (trim)
print("  hello  ".strip())  # "hello"
 
# Replace
print(s.replace("World", "Python"))  # "Hello, Python!"

// TypeScript - Two Sum using Hash Map - O(n)
function twoSum(nums: number[], target: number): number[] {
  const seen = new Map<number, number>();
 
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
 
    if (seen.has(complement)) {
      return [seen.get(complement)!, i];
    }
 
    seen.set(nums[i], i);
  }
 
  return [-1, -1];
}
 
console.log(twoSum([2, 7, 11, 15], 9)); // [0, 1]
console.log(twoSum([3, 2, 4], 6));      // [1, 2]

# Python - Two Sum using Hash Map - O(n)
def two_sum(nums: list[int], target: int) -> list[int]:
    seen = {}
 
    for i, num in enumerate(nums):
        complement = target - num
 
        if complement in seen:
            return [seen[complement], i]
 
        seen[num] = i
 
    return [-1, -1]
 
print(two_sum([2, 7, 11, 15], 9))  # [0, 1]
print(two_sum([3, 2, 4], 6))       # [1, 2]

// TypeScript - Kadane's Algorithm - O(n)
function maxSubArray(nums: number[]): number {
  let maxSum = nums[0];
  let currentSum = nums[0];
 
  for (let i = 1; i < nums.length; i++) {
    // Either extend current subarray or start new one
    currentSum = Math.max(nums[i], currentSum + nums[i]);
    maxSum = Math.max(maxSum, currentSum);
  }
 
  return maxSum;
}
 
console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])); // 6 ([4,-1,2,1])
console.log(maxSubArray([1])); // 1
console.log(maxSubArray([-1, -2, -3])); // -1

# Python - Kadane's Algorithm - O(n)
def max_sub_array(nums: list[int]) -> int:
    max_sum = nums[0]
    current_sum = nums[0]
 
    for i in range(1, len(nums)):
        current_sum = max(nums[i], current_sum + nums[i])
        max_sum = max(max_sum, current_sum)
 
    return max_sum
 
print(max_sub_array([-2, 1, -3, 4, -1, 2, 1, -5, 4]))  # 6

// TypeScript - Merge Sorted Arrays - O(n + m)
function mergeSortedArrays(nums1: number[], nums2: number[]): number[] {
  const result: number[] = [];
  let i = 0, j = 0;
 
  while (i < nums1.length && j < nums2.length) {
    if (nums1[i] <= nums2[j]) {
      result.push(nums1[i]);
      i++;
    } else {
      result.push(nums2[j]);
      j++;
    }
  }
 
  // Add remaining elements
  while (i < nums1.length) {
    result.push(nums1[i]);
    i++;
  }
 
  while (j < nums2.length) {
    result.push(nums2[j]);
    j++;
  }
 
  return result;
}
 
console.log(mergeSortedArrays([1, 3, 5], [2, 4, 6])); // [1, 2, 3, 4, 5, 6]

# Python - Merge Sorted Arrays - O(n + m)
def merge_sorted_arrays(nums1: list[int], nums2: list[int]) -> list[int]:
    result = []
    i, j = 0, 0
 
    while i < len(nums1) and j < len(nums2):
        if nums1[i] <= nums2[j]:
            result.append(nums1[i])
            i += 1
        else:
            result.append(nums2[j])
            j += 1
 
    # Add remaining elements
    result.extend(nums1[i:])
    result.extend(nums2[j:])
 
    return result
 
print(merge_sorted_arrays([1, 3, 5], [2, 4, 6]))  # [1, 2, 3, 4, 5, 6]

// TypeScript - Rotate Array - O(n) time, O(1) space
function rotate(nums: number[], k: number): void {
  k = k % nums.length;  // Handle k > length
 
  // Reverse entire array
  reverse(nums, 0, nums.length - 1);
  // Reverse first k elements
  reverse(nums, 0, k - 1);
  // Reverse remaining elements
  reverse(nums, k, nums.length - 1);
}
 
function reverse(nums: number[], start: number, end: number): void {
  while (start < end) {
    [nums[start], nums[end]] = [nums[end], nums[start]];
    start++;
    end--;
  }
}
 
const arr = [1, 2, 3, 4, 5, 6, 7];
rotate(arr, 3);
console.log(arr); // [5, 6, 7, 1, 2, 3, 4]

# Python - Rotate Array - O(n) time, O(1) space
def rotate(nums: list[int], k: int) -> None:
    k = k % len(nums)
 
    def reverse(start: int, end: int) -> None:
        while start < end:
            nums[start], nums[end] = nums[end], nums[start]
            start += 1
            end -= 1
 
    # Reverse entire array
    reverse(0, len(nums) - 1)
    # Reverse first k elements
    reverse(0, k - 1)
    # Reverse remaining elements
    reverse(k, len(nums) - 1)
 
arr = [1, 2, 3, 4, 5, 6, 7]
rotate(arr, 3)
print(arr)  # [5, 6, 7, 1, 2, 3, 4]

// TypeScript - Valid Palindrome - O(n)
function isPalindrome(s: string): boolean {
  let left = 0;
  let right = s.length - 1;
 
  while (left < right) {
    // Skip non-alphanumeric
    while (left < right && !isAlphanumeric(s[left])) {
      left++;
    }
    while (left < right && !isAlphanumeric(s[right])) {
      right--;
    }
 
    if (s[left].toLowerCase() !== s[right].toLowerCase()) {
      return false;
    }
 
    left++;
    right--;
  }
 
  return true;
}
 
function isAlphanumeric(char: string): boolean {
  return /[a-zA-Z0-9]/.test(char);
}
 
console.log(isPalindrome("A man, a plan, a canal: Panama")); // true
console.log(isPalindrome("race a car")); // false

# Python - Valid Palindrome - O(n)
def is_palindrome(s: str) -> bool:
    left, right = 0, len(s) - 1
 
    while left < right:
        # Skip non-alphanumeric
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
 
        if s[left].lower() != s[right].lower():
            return False
 
        left += 1
        right -= 1
 
    return True
 
print(is_palindrome("A man, a plan, a canal: Panama"))  # True
print(is_palindrome("race a car"))  # False

// TypeScript - Valid Anagram using frequency count - O(n)
function isAnagram(s: string, t: string): boolean {
  if (s.length !== t.length) return false;
 
  const count = new Map<string, number>();
 
  // Count characters in s
  for (const char of s) {
    count.set(char, (count.get(char) || 0) + 1);
  }
 
  // Subtract characters in t
  for (const char of t) {
    const currentCount = count.get(char);
    if (!currentCount) return false;
 
    if (currentCount === 1) {
      count.delete(char);
    } else {
      count.set(char, currentCount - 1);
    }
  }
 
  return count.size === 0;
}
 
console.log(isAnagram("anagram", "nagaram")); // true
console.log(isAnagram("rat", "car")); // false

# Python - Valid Anagram using Counter - O(n)
from collections import Counter
 
def is_anagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    return Counter(s) == Counter(t)
 
print(is_anagram("anagram", "nagaram"))  # True
print(is_anagram("rat", "car"))  # False
 
# Alternative without Counter
def is_anagram_manual(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
 
    count = {}
 
    for char in s:
        count[char] = count.get(char, 0) + 1
 
    for char in t:
        if char not in count:
            return False
        count[char] -= 1
        if count[char] == 0:
            del count[char]
 
    return len(count) == 0

// TypeScript - Longest Common Prefix - O(S) where S is sum of all characters
function longestCommonPrefix(strs: string[]): string {
  if (strs.length === 0) return "";
 
  let prefix = strs[0];
 
  for (let i = 1; i < strs.length; i++) {
    while (strs[i].indexOf(prefix) !== 0) {
      prefix = prefix.slice(0, -1);  // Remove last character
      if (prefix === "") return "";
    }
  }
 
  return prefix;
}
 
console.log(longestCommonPrefix(["flower", "flow", "flight"])); // "fl"
console.log(longestCommonPrefix(["dog", "racecar", "car"]));    // ""

# Python - Longest Common Prefix
def longest_common_prefix(strs: list[str]) -> str:
    if not strs:
        return ""
 
    prefix = strs[0]
 
    for s in strs[1:]:
        while not s.startswith(prefix):
            prefix = prefix[:-1]  # Remove last character
            if not prefix:
                return ""
 
    return prefix
 
print(longest_common_prefix(["flower", "flow", "flight"]))  # "fl"
print(longest_common_prefix(["dog", "racecar", "car"]))     # ""

// TypeScript - String Compression
function compress(chars: string[]): number {
  let write = 0;
  let read = 0;
 
  while (read < chars.length) {
    const char = chars[read];
    let count = 0;
 
    // Count consecutive chars
    while (read < chars.length && chars[read] === char) {
      read++;
      count++;
    }
 
    // Write character
    chars[write] = char;
    write++;
 
    // Write count if > 1
    if (count > 1) {
      const countStr = count.toString();
      for (const digit of countStr) {
        chars[write] = digit;
        write++;
      }
    }
  }
 
  return write;
}
 
const chars = ["a", "a", "b", "b", "c", "c", "c"];
const length = compress(chars);
console.log(chars.slice(0, length).join("")); // "a2b2c3"

# Python - String Compression
def compress(chars: list[str]) -> int:
    write = 0
    read = 0
 
    while read < len(chars):
        char = chars[read]
        count = 0
 
        # Count consecutive chars
        while read < len(chars) and chars[read] == char:
            read += 1
            count += 1
 
        # Write character
        chars[write] = char
        write += 1
 
        # Write count if > 1
        if count > 1:
            for digit in str(count):
                chars[write] = digit
                write += 1
 
    return write
 
chars = ["a", "a", "b", "b", "c", "c", "c"]
length = compress(chars)
print("".join(chars[:length]))  # "a2b2c3"

// TypeScript - Essential array methods
 
// map - Transform each element
const doubled = [1, 2, 3].map(x => x * 2);  // [2, 4, 6]
 
// filter - Keep elements that pass test
const evens = [1, 2, 3, 4, 5].filter(x => x % 2 === 0);  // [2, 4]
 
// reduce - Accumulate to single value
const sum = [1, 2, 3, 4].reduce((acc, x) => acc + x, 0);  // 10
 
// find - First element that passes test
const found = [1, 2, 3, 4].find(x => x > 2);  // 3
 
// findIndex - Index of first matching element
const index = [1, 2, 3, 4].findIndex(x => x > 2);  // 2
 
// some - At least one element passes test
const hasEven = [1, 2, 3].some(x => x % 2 === 0);  // true
 
// every - All elements pass test
const allPositive = [1, 2, 3].every(x => x > 0);  // true
 
// includes - Check if element exists
const hasThree = [1, 2, 3].includes(3);  // true
 
// slice - Extract portion (non-mutating)
const portion = [1, 2, 3, 4, 5].slice(1, 4);  // [2, 3, 4]
 
// splice - Add/remove elements (mutating!)
const arr = [1, 2, 3, 4, 5];
arr.splice(2, 1);  // Remove 1 element at index 2
console.log(arr);  // [1, 2, 4, 5]
 
// concat - Combine arrays
const combined = [1, 2].concat([3, 4]);  // [1, 2, 3, 4]
 
// flat - Flatten nested arrays
const flattened = [[1, 2], [3, 4]].flat();  // [1, 2, 3, 4]
 
// sort - Sort array (mutating!)
const sorted = [3, 1, 4, 1, 5].sort((a, b) => a - b);  // [1, 1, 3, 4, 5]

# Python - Essential list methods
 
# append - Add to end
arr = [1, 2, 3]
arr.append(4)  # [1, 2, 3, 4]
 
# extend - Add multiple elements
arr.extend([5, 6])  # [1, 2, 3, 4, 5, 6]
 
# insert - Insert at index
arr.insert(0, 0)  # [0, 1, 2, 3, 4, 5, 6]
 
# remove - Remove first occurrence of value
arr.remove(3)  # [0, 1, 2, 4, 5, 6]
 
# pop - Remove at index (default: last)
arr.pop()     # Returns 6, arr = [0, 1, 2, 4, 5]
arr.pop(0)    # Returns 0, arr = [1, 2, 4, 5]
 
# index - Find index of value
arr.index(4)  # 2
 
# count - Count occurrences
[1, 2, 2, 3].count(2)  # 2
 
# sort - Sort in place
arr.sort()  # [1, 2, 4, 5]
 
# sorted - Return new sorted list
sorted([3, 1, 4, 1, 5])  # [1, 1, 3, 4, 5]
 
# reverse - Reverse in place
arr.reverse()  # [5, 4, 2, 1]
 
# List comprehension - Pythonic way to transform
doubled = [x * 2 for x in [1, 2, 3]]  # [2, 4, 6]
evens = [x for x in range(10) if x % 2 == 0]  # [0, 2, 4, 6, 8]
 
# Slicing
arr = [0, 1, 2, 3, 4, 5]
arr[1:4]    # [1, 2, 3]
arr[::2]    # [0, 2, 4] (every 2nd element)
arr[::-1]   # [5, 4, 3, 2, 1, 0] (reversed)