Arrays & Strings

Arrays and strings are the most fundamental data structures in programming. They represent contiguous blocks of memory storing elements of the same type (arrays) or characters (strings).

Key properties:

• Random access: O(1) time to access any element by index
• Fixed size (arrays): Cannot grow or shrink (in most languages)
• Mutable/Immutable: Arrays are typically mutable; strings may be immutable (Java, Python) or mutable (C++)
• Cache-friendly: Sequential memory layout enables fast iteration

Understanding arrays and strings is crucial because they appear in ~40% of all coding interview problems.

• Foundation for other structures: Stacks, queues, heaps, hash tables all use arrays internally

  • Interview frequency: Most common data structure in technical interviews
  • Pattern recognition: Many advanced algorithms (DP, greedy, sliding window) operate on arrays
  • Real-world applications: Text processing, data analysis, image manipulation, signal processing

  Performance characteristics:

  • Access: O(1)
  • Search: O(n) unsorted, O(log n) sorted
  • Insert/Delete: O(n) (requires shifting elements)
  • Space: O(n)

Use arrays when you need:

1. Fast random access by index
2. Sequential data with known or bounded size
3. Cache-efficient iteration over elements
4. Simple implementation without overhead

Use strings when working with:

1. Text processing: parsing, pattern matching, validation
2. Character manipulation: reversals, rotations, transformations
3. Encoding/decoding: compression, encryption, serialization
4. Substring problems: palindromes, anagrams, subsequences

Common problem types:

• Two pointers (opposite ends, same direction)
• Sliding window (fixed/variable size)
• Prefix/suffix arrays (cumulative sums, products)
• In-place modifications (space optimization)
• Sorting and searching

1. Two Pointers Use two indices to traverse the array from different positions:

• Opposite ends: palindrome check, two sum in sorted array
• Same direction: remove duplicates, partition

2. Sliding Window Maintain a window of elements and slide it across the array:

• Fixed size: max sum of k elements
• Variable size: longest substring without repeating chars

3. Prefix/Suffix Precompute cumulative information:

• Prefix sums: range sum queries in O(1)
• Prefix XOR: subarray XOR queries
• Suffix products: product except self

4. In-place Modification Modify array without extra space:

• Swap elements
• Use array indices as hash keys
• Mark visited elements by negating

Subarray problems:

• Maximum subarray sum (Kadane's algorithm)
• Longest subarray with sum ≤ k
• Count subarrays with given property

Substring problems:

• Longest substring without repeating characters
• Minimum window substring
• Anagram detection

Sorting-based:

• Merge intervals
• Meeting rooms
• 3Sum, 4Sum

Binary search:

• Search in rotated sorted array
• Find peak element
• Search for range

• Off-by-one errors: Carefully handle array boundaries (0 to n-1)
  • String immutability: In Java/Python, string concatenation in loops is O(n²)—use StringBuilder/list
  • Integer overflow: Sum of array elements may exceed int range
  • Modifying while iterating: Can cause unexpected behavior or infinite loops
  • Not considering edge cases: Empty array, single element, all same elements
  • Space complexity: In-place algorithms should use O(1) extra space, not O(n)

1. Need to find pairs/triplets? → Two pointers or hash map
2. Contiguous subarray/substring? → Sliding window or prefix sum
3. Need to sort first? → Consider if sorting helps (intervals, 3Sum)
4. Search in sorted array? → Binary search
5. Need O(1) space? → In-place modification techniques
6. Character frequency? → Hash map or fixed-size array (26 letters)
7. Palindrome check? → Two pointers from ends
8. Rotation/reversal? → Reverse in parts