Arrays & Strings

Arrays and Strings are the most fundamental data structures in programming. An array is a collection of elements stored in contiguous memory locations, while a string is essentially an array of characters.

Why are they important for interviews?

About 40% of coding interview questions involve arrays or strings. They test your ability to:

• •Think about edge cases (empty arrays, single elements)
• •Optimize time and space complexity
• •Use built-in methods efficiently
• •Apply various algorithmic techniques

Array Basics:

• •Access: O(1) - Direct access using index
• •Search: O(n) - Linear search, O(log n) if sorted (binary search)
• •Insert/Delete: O(n) - Need to shift elements
• •Space: O(n) - Stores n elements

String Basics:

• •Strings are immutable in most languages (Java, Python, JavaScript)
• •String concatenation in a loop is O(n²) - use StringBuilder/join instead
• •Character comparisons are O(1)

The Hash Map is your best friend for array problems. It provides O(1) average time for lookups, insertions, and deletions.

When to use Hash Map:

1. •Finding pairs: Two Sum, finding complement
2. •Counting frequencies: Character count, duplicate detection
3. •Grouping elements: Group Anagrams, grouping by property
4. •Tracking seen elements: Contains Duplicate
5. •Storing prefix sums: Subarray sum problems

How it works:

Time vs Space Tradeoff:

• •Without HashMap: O(n²) time, O(1) space (check all pairs)
• •With HashMap: O(n) time, O(n) space

This is a classic example of trading space for time efficiency.

Watch how the hash map stores values and finds complements in O(1) time.

Counting how often each element appears is one of the most common array/string operations.

Common Use Cases:

1. •Valid Anagram: Check if two strings have same character frequencies
2. •Find duplicates: Count > 1 means duplicate
3. •Find majority element: Count > n/2
4. •First unique character: Count == 1

Visualization:

For lowercase letters only, you can use an array of size 26 instead of HashMap:

• •More memory efficient
• •Slightly faster (no hashing overhead)
• •Index = character - 'a'

Prefix arrays let you answer range queries in O(1) time after O(n) preprocessing.

Prefix Sum: Store cumulative sum up to each index.

Prefix Product: Store cumulative product up to each index.

Key Insight for "Product Except Self":

• •Can't use division (zeros in array)
• •Solution: Multiply prefix product * suffix product
• •Can do in O(1) space by computing suffix on-the-fly

Watch how prefix sums are built and used to answer range queries in O(1) time.

Kadane's Algorithm finds the maximum sum contiguous subarray in O(n) time. It's a beautiful example of dynamic programming.

The Key Insight: At each position, we make a simple decision:

• •Should we extend the previous subarray?
• •Or start a new subarray from here?

We extend if the previous sum is positive (it helps). We start fresh if it's negative (it hurts).

Visualization:

Formula: currentSum = max(nums[i], currentSum + nums[i])

See how Kadane's algorithm decides whether to extend or start a new subarray at each step.

Many problems ask you to count or find subarrays with a specific sum. The key insight is using prefix sums with a HashMap.

Why does this work? If prefixSum[j] - prefixSum[i] = k, then the subarray from i+1 to j has sum k.

Visualization:

Key Points:

1. •Initialize map with {0: 1} for empty prefix
2. •For each position, check if (currentSum - k) exists
3. •Count how many times that prefix sum occurred
4. •Add current prefix sum to map

When dealing with numbers in a specific range (1 to n), you can use the array indices themselves as a hash map. This gives O(1) space complexity!

The Idea: Place each number at its "correct" index:

• •Number 1 should be at index 0
• •Number 2 should be at index 1
• •Number k should be at index k-1

Visualization:

When to use:

• •Find missing number in range
• •Find duplicate in range
• •First missing positive
• •Find all duplicates/missing

Strings have their own set of patterns and gotchas. Here are the key techniques:

1. Two Pointer for Palindromes: Compare characters from both ends moving inward.

2. StringBuilder for Concatenation: Never concatenate strings in a loop - it's O(n²)!

3. Character Array for In-place: Convert to char[] to modify characters.

4. Sorting as a Key: Anagrams have the same sorted form.

5. ASCII/Unicode Values: Use character codes for calculations.

Common String Problems:

Sometimes you need to modify an array without using extra space. This requires careful pointer manipulation.

Common Techniques:

1. Two-Pointer Swap: Used for partitioning, moving elements.

2. Overwrite from Start: Used for removing duplicates, filtering.

3. Reverse Sections: Used for rotating arrays.

Rotate Array Example:

Remove Duplicates:

Here's a decision guide for choosing the right technique:

Finding Elements:

Subarray Problems:

Modifying Arrays:

String Problems:

Remember:

• •O(n²) -> O(n): Usually needs HashMap or sorting
• •O(n) space -> O(1): Usually needs in-place techniques
• •Range queries: Consider prefix sum/product
• •Numbers in [1,n]: Consider cyclic sort