DSA

Arrays & Strings

Interview Prep · 8 entries

Two Pointers Technique

Syntax

Use two indices (left and right) moving toward each other or in the same direction.
Works on sorted arrays or when searching for pairs.

Example

// JavaScript - Find pair that sums to target in sorted array
function twoSumSorted(arr, target) {
  let left = 0, right = arr.length - 1;
  while (left < right) {
    const sum = arr[left] + arr[right];
    if (sum === target) return [left, right];
    else if (sum < target) left++;
    else right--;
  }
  return [-1, -1];
}

# Python
def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        total = arr[left] + arr[right]
        if total == target:
            return [left, right]
        elif total < target:
            left += 1
        else:
            right -= 1
    return [-1, -1]

Output

twoSumSorted([1,3,5,7,9], 8) → [1, 3]

Note Time O(n), Space O(1). Requires sorted input for the converging pattern. Edge cases: empty array, single element, no valid pair. Tell the interviewer you chose two pointers over hash map to achieve O(1) space.

two pointerssorted array pairtwo sum sortedconverging pointers

Sliding Window

Syntax

Maintain a window [left..right] and expand/shrink to satisfy a condition.
Fixed-size window: move both pointers together.
Variable-size window: expand right, shrink left when constraint violated.

Example

// JavaScript - Max sum subarray of size k
function maxSumWindow(arr, k) {
  let windowSum = 0, maxSum = -Infinity;
  for (let i = 0; i < arr.length; i++) {
    windowSum += arr[i];
    if (i >= k) windowSum -= arr[i - k];
    if (i >= k - 1) maxSum = Math.max(maxSum, windowSum);
  }
  return maxSum;
}

# Python - Max sum subarray of size k
def max_sum_window(arr, k):
    window_sum = 0
    max_sum = float('-inf')
    for i in range(len(arr)):
        window_sum += arr[i]
        if i >= k:
            window_sum -= arr[i - k]
        if i >= k - 1:
            max_sum = max(max_sum, window_sum)
    return max_sum

Output

max_sum_window([2,1,5,1,3,2], 3) → 9 (subarray [5,1,3])

Note Time O(n), Space O(1). Sliding window converts O(n*k) brute force to O(n). For variable-size windows (e.g., longest substring without repeats), use a hash set to track window contents. Always clarify: is the window fixed or variable size?

sliding window max sum subarrayfixed windowvariable window substring

Prefix Sum

Syntax

Build a cumulative sum array so any range sum can be computed in O(1).
prefix[i] = sum of arr[0..i-1]
Range sum [l..r] = prefix[r+1] - prefix[l]

Example

// JavaScript
function buildPrefix(arr) {
  const prefix = [0];
  for (const val of arr) {
    prefix.push(prefix[prefix.length - 1] + val);
  }
  return prefix;
}
function rangeSum(prefix, left, right) {
  return prefix[right + 1] - prefix[left];
}

# Python
def build_prefix(arr):
    prefix = [0]
    for val in arr:
        prefix.append(prefix[-1] + val)
    return prefix

def range_sum(prefix, left, right):
    return prefix[right + 1] - prefix[left]

Output

arr=[3,1,4,1,5] → prefix=[0,3,4,8,9,14]
rangeSum(1,3) = prefix[4]-prefix[1] = 9-3 = 6

Note Build: O(n) time, O(n) space. Query: O(1). Extremely useful when you need many range sum queries. Variant: prefix XOR for range XOR problems. For 2D grids, use 2D prefix sums with inclusion-exclusion.

prefix sumrange sum querycumulative sum subarray sum

Kadane's Algorithm - Maximum Subarray

Syntax

Track current subarray sum. If it drops below 0, reset to 0.
At each step: currentSum = max(num, currentSum + num)
Keep a global max.

Example

// JavaScript
function maxSubarraySum(arr) {
  let current = arr[0], best = arr[0];
  for (let i = 1; i < arr.length; i++) {
    current = Math.max(arr[i], current + arr[i]);
    best = Math.max(best, current);
  }
  return best;
}

# Python
def max_subarray_sum(arr):
    current = best = arr[0]
    for num in arr[1:]:
        current = max(num, current + num)
        best = max(best, current)
    return best

Output

max_subarray_sum([-2,1,-3,4,-1,2,1,-5,4]) → 6 (subarray [4,-1,2,1])

Note Time O(n), Space O(1). Edge case: all negative numbers - algorithm still works since we initialize with arr[0]. To find the actual subarray indices, track start/end when best updates. Variant: maximum circular subarray uses total_sum - min_subarray.

kadane's algorithmmaximum subarraymax subarray sumcontiguous subarray

Binary Search on Sorted Array

Syntax

lo = 0, hi = length - 1
while lo <= hi:
  mid = lo + (hi - lo) // 2
  compare and adjust lo or hi

Example

// JavaScript
function binarySearch(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1; // not found
}

# Python
def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Output

binary_search([1,3,5,7,9,11], 7) → 3

Note Time O(log n), Space O(1). Off-by-one errors are the #1 bug - practice until the template is muscle memory. Use lo <= hi when searching for exact match. Use lo < hi when narrowing to a single candidate. Always test with 0, 1, and 2 element arrays.

binary searchsorted arraysearch algorithmlog n

String Reversal

Syntax

Two pointers from ends, swap toward center.
Or use built-in reverse methods.

Example

// JavaScript
function reverseString(s) {
  const chars = s.split('');
  let l = 0, r = chars.length - 1;
  while (l < r) {
    [chars[l], chars[r]] = [chars[r], chars[l]];
    l++; r--;
  }
  return chars.join('');
}
// Built-in: s.split('').reverse().join('')

# Python
def reverse_string(s):
    chars = list(s)
    l, r = 0, len(chars) - 1
    while l < r:
        chars[l], chars[r] = chars[r], chars[l]
        l += 1; r -= 1
    return ''.join(chars)
# Built-in: s[::-1]

Output

reverseString('interview') → 'weivretni'

Note Time O(n), Space O(n) due to string immutability (both JS and Python strings are immutable). In-place reversal is possible on char arrays. Common follow-ups: reverse words in a sentence, reverse only vowels, check if palindrome.

reverse string string reversalpalindrometwo pointers string

Anagram Detection

Syntax

Two strings are anagrams if they have identical character frequencies.
Approach 1: Sort both and compare.
Approach 2: Build frequency map and compare.

Example

// JavaScript
function isAnagram(s, t) {
  if (s.length !== t.length) return false;
  const freq = {};
  for (const ch of s) freq[ch] = (freq[ch] || 0) + 1;
  for (const ch of t) {
    if (!freq[ch]) return false;
    freq[ch]--;
  }
  return true;
}

# Python
def is_anagram(s, t):
    if len(s) != len(t):
        return False
    freq = {}
    for ch in s:
        freq[ch] = freq.get(ch, 0) + 1
    for ch in t:
        if freq.get(ch, 0) == 0:
            return False
        freq[ch] -= 1
    return True

Output

is_anagram('listen', 'silent') → True

Note Frequency map: O(n) time, O(1) space (bounded by alphabet size). Sorting approach: O(n log n). Always ask: are inputs lowercase only? Unicode? This affects space analysis. Follow-up: find all anagram groups in a list of words.

anagram detectionis anagramcharacter frequencygroup anagrams

Finding Duplicates

Syntax

Approach 1: Hash set - O(n) time, O(n) space
Approach 2: Sort first - O(n log n) time, O(1) space
Approach 3: Floyd's cycle (special constraints) - O(n) time, O(1) space

Example

// JavaScript - Hash set approach
function containsDuplicate(arr) {
  const seen = new Set();
  for (const val of arr) {
    if (seen.has(val)) return true;
    seen.add(val);
  }
  return false;
}

function findDuplicate(arr) {
  // Values in range [1, n], exactly one duplicate
  const seen = new Set();
  for (const val of arr) {
    if (seen.has(val)) return val;
    seen.add(val);
  }
}

# Python
def contains_duplicate(arr):
    seen = set()
    for val in arr:
        if val in seen:
            return True
        seen.add(val)
    return False

def find_duplicate(arr):
    seen = set()
    for val in arr:
        if val in seen:
            return val
        seen.add(val)

Output

contains_duplicate([1,2,3,1]) → True
find_duplicate([1,3,4,2,2]) → 2

Note The hash set approach is the go-to. If asked for O(1) space with values in [1,n], use Floyd's tortoise and hare or index marking (negate values). Always clarify constraints: can you modify the input? What is the value range?

find duplicatescontains duplicatehash setduplicate detection