Arrays and Strings Basics

Arrays and strings are the most fundamental data structures in coding interviews. Nearly every problem involves manipulating them in some way. Mastering their operations and time complexities is non-negotiable.

Arrays

An array is a contiguous block of memory storing elements of the same type. Arrays provide O(1) random access by index but O(n) insertion and deletion (shifting required).

Time Complexity

Common Patterns

// Two Sum : O(n) with hash map
function twoSum(nums: number[], target: number): number[] {
  const map = new Map<number, number>();
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (map.has(complement)) return [map.get(complement)!, i];
    map.set(nums[i], i);
  }
  return [];
}

Strings

Strings are arrays of characters. In most languages, strings are immutable (creating a new string on modification costs O(n)). In Python, strings are immutable. In Java, use StringBuilder for efficient concatenation.

String Manipulation Techniques

• Character frequency count: Use an array of size 26 (for lowercase) or a hash map.
• Reversal: Two pointers from both ends, swapping until they meet. O(n) time, O(1) space.
• Anagram check: Sort both strings and compare, or use character frequency counts.
• Palindrome check: Two pointers from both ends, comparing characters moving inward.

// Check if string is palindrome
function isPalindrome(s: string): boolean {
  let left = 0, right = s.length - 1;
  while (left < right) {
    if (s[left] !== s[right]) return false;
    left++;
    right--;
  }
  return true;
}

In-Place Array Operations

Interviewers often ask for O(1) extra space solutions. Key technique: use the array itself as a hash map by storing values at specific indices.

// Remove duplicates from sorted array : O(1) space
function removeDuplicates(nums: number[]): number {
  let write = 1;
  for (let read = 1; read < nums.length; read++) {
    if (nums[read] !== nums[read - 1]) {
      nums[write] = nums[read];
      write++;
    }
  }
  return write;
}

Common Mistakes

• Off-by-one errors : always clarify whether the array is 0-indexed and whether the range is inclusive or exclusive.
• Modifying an array while iterating : use a separate read/write pointer or collect modifications first.
• Ignoring edge cases : empty arrays, single elements, all identical elements.
• Using extra space when O(1) is required : think about in-place techniques before reaching for a hash map.
• Not asking about constraints : the optimal approach depends on whether the array is sorted, whether duplicates exist, and the size of the input.