Arrays & Strings — Patterns & Problems

function twoSum(nums: number[], target: number): number[] {
  let left = 0, right = nums.length - 1;

  while (left < right) {
    const sum = nums[left] + nums[right];
    if (sum === target) return [left, right];
    if (sum < target)  left++;
    else               right--;
  }

  return [];
}
// Time: O(n) | Space: O(1)

function isPalindrome(s: string): boolean {
  // Keep only alphanumeric characters, lowercase
  const cleaned = s.toLowerCase().replace(/[^a-z0-9]/g, '');
  let left = 0, right = cleaned.length - 1;

  while (left < right) {
    if (cleaned[left] !== cleaned[right]) return false;
    left++;
    right--;
  }

  return true;
}
// Time: O(n) | Space: O(n) for cleaned string

function removeDuplicates(nums: number[]): number {
  if (nums.length === 0) return 0;

  let write = 1;  // next position to write a new unique value

  for (let read = 1; read < nums.length; read++) {
    if (nums[read] !== nums[write - 1]) {
      nums[write] = nums[read];
      write++;
    }
  }

  return write;
}
// Time: O(n) | Space: O(1)

function maxArea(height: number[]): number {
  let left = 0, right = height.length - 1;
  let maxWater = 0;

  while (left < right) {
    const width = right - left;
    const water = Math.min(height[left], height[right]) * width;
    maxWater = Math.max(maxWater, water);

    // Move the pointer with the smaller height — it can only get worse if we don't
    if (height[left] < height[right]) left++;
    else                              right--;
  }

  return maxWater;
}
// Time: O(n) | Space: O(1)

function maxSumSubarray(nums: number[], k: number): number {
  let windowSum = nums.slice(0, k).reduce((a, b) => a + b, 0);
  let maxSum = windowSum;

  for (let i = k; i < nums.length; i++) {
    windowSum += nums[i] - nums[i - k];  // slide: add new, remove old
    maxSum = Math.max(maxSum, windowSum);
  }

  return maxSum;
}
// Time: O(n) | Space: O(1)

function lengthOfLongestSubstring(s: string): number {
  const seen = new Map<string, number>();  // char → last seen index
  let left = 0, maxLen = 0;

  for (let right = 0; right < s.length; right++) {
    const char = s[right];

    // If char was seen and is still inside our window, shrink from left
    if (seen.has(char) && seen.get(char)! >= left) {
      left = seen.get(char)! + 1;
    }

    seen.set(char, right);
    maxLen = Math.max(maxLen, right - left + 1);
  }

  return maxLen;
}
// Time: O(n) | Space: O(min(n, alphabet))

function minSubArrayLen(target: number, nums: number[]): number {
  let left = 0, sum = 0, minLen = Infinity;

  for (let right = 0; right < nums.length; right++) {
    sum += nums[right];

    // Shrink window from left while sum is sufficient
    while (sum >= target) {
      minLen = Math.min(minLen, right - left + 1);
      sum -= nums[left];
      left++;
    }
  }

  return minLen === Infinity ? 0 : minLen;
}
// Time: O(n) | Space: O(1)

class NumArray {
  private prefix: number[];

  constructor(nums: number[]) {
    this.prefix = new Array(nums.length + 1).fill(0);
    for (let i = 0; i < nums.length; i++) {
      this.prefix[i + 1] = this.prefix[i] + nums[i];
    }
  }

  sumRange(left: number, right: number): number {
    return this.prefix[right + 1] - this.prefix[left];
  }
}
// Build: O(n) | Query: O(1)

function subarraySum(nums: number[], k: number): number {
  const prefixCount = new Map<number, number>([[0, 1]]);
  let sum = 0, count = 0;

  for (const num of nums) {
    sum += num;
    // If sum - k exists as a prefix sum, those subarrays equal k
    count += prefixCount.get(sum - k) ?? 0;
    prefixCount.set(sum, (prefixCount.get(sum) ?? 0) + 1);
  }

  return count;
}
// Time: O(n) | Space: O(n)

function twoSum(nums: number[], target: number): number[] {
  const seen = new Map<number, number>();  // value → index

  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 [];
}
// Time: O(n) | Space: O(n)

function groupAnagrams(strs: string[]): string[][] {
  const map = new Map<string, string[]>();

  for (const str of strs) {
    const key = str.split('').sort().join('');  // sorted chars = anagram key
    if (!map.has(key)) map.set(key, []);
    map.get(key)!.push(str);
  }

  return [...map.values()];
}
// Time: O(n × m log m) where m = avg string length | Space: O(n)

function merge(intervals: number[][]): number[][] {
  intervals.sort((a, b) => a[0] - b[0]);  // sort by start time
  const result: number[][] = [intervals[0]];

  for (let i = 1; i < intervals.length; i++) {
    const last    = result[result.length - 1];
    const current = intervals[i];

    if (current[0] <= last[1]) {
      // Overlap — extend the end of the last interval
      last[1] = Math.max(last[1], current[1]);
    } else {
      result.push(current);
    }
  }

  return result;
}
// Time: O(n log n) | Space: O(n)

function reverseString(s: string[]): void {
  let left = 0, right = s.length - 1;
  while (left < right) {
    [s[left], s[right]] = [s[right], s[left]];
    left++; right--;
  }
}

function isAnagram(s: string, t: string): boolean {
  if (s.length !== t.length) return false;

  const freq = new Array(26).fill(0);
  const a = 'a'.charCodeAt(0);

  for (let i = 0; i < s.length; i++) {
    freq[s.charCodeAt(i) - a]++;
    freq[t.charCodeAt(i) - a]--;
  }

  return freq.every(c => c === 0);
}
// Time: O(n) | Space: O(1) — fixed-size array

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].startsWith(prefix)) {
      prefix = prefix.slice(0, -1);
      if (prefix === '') return '';
    }
  }

  return prefix;
}
// Time: O(n × m) | Space: O(1)

Sorted array + pair search      → Two pointers (left/right from ends)
Subarray/substring + contiguous → Sliding window
Range sum queries               → Prefix sum array
"Find if exists" or "count"     → Hash map/set
Overlapping intervals           → Sort + greedy merge
Anagram / frequency check       → Char frequency array or map

Complexity targets:
  Brute force:   O(n²) with nested loops
  Optimal:       O(n) with hash map or O(n log n) with sort
  Two pointers:  O(n) time, O(1) space
  Sliding window: O(n) time, O(k) space
  Prefix sum:    O(n) build, O(1) query