Arrays & Strings Interview Questions

The foundation of coding interviews. 40+ highly-asked questions with complete solutions. Focus: Two Pointers, Sliding Window, and O(1) space optimizations.

Core Array Algorithms

1. Two Sum: Given an array and a target, return indices of the two numbers such that they add up to the target. Easy

Answer & Explanation

Optimal Technique: Hash Map (or Dictionary). This approach allows us to reduce the search time from O(n) (in a brute force approach) to O(1) for each element, achieving an overall time complexity of O(n).

Steps:

  1. Initialize an empty hash map numMap to store (number, index) pairs encountered so far.
  2. Iterate through the array. For each number num, calculate the complement = target - num.
  3. Check if the complement already exists as a key in numMap. If it does, we have found the pair. Return [numMap[complement], current_index].
  4. If the complement is not found, add the current number and its index to the map: numMap[num] = current_index.

Complexity: Time: O(n). Space: O(n).

2. Container With Most Water: Find two lines that together with the x-axis form a container that contains the most water. Medium

Answer & Explanation

Optimal Technique: Two-Pointer approach. Start with pointers at the extreme ends (widest possible container) and greedily move the pointer associated with the shorter line inward.

Rationale: The area is calculated as $Area = \min(\text{height}[\text{left}], \text{height}[\text{right}]) \times (\text{right} - \text{left})$. Starting wide maximizes the width. To increase the area, you must increase the minimum height. Moving the shorter line gives a better chance of finding a taller boundary compared to moving the already taller one (which would only reduce the width).

Complexity: Time: O(n). Space: O(1).

3. Sort an array of 0s, 1s, and 2s without using a sorting algorithm (Dutch National Flag problem). Medium

Answer & Explanation

Technique: Three-pointer Partition (Dijkstra's Three-Way Partitioning). Use three pointers: low (boundary for 0s), mid (current element), and high (boundary for 2s).

  • If arr[mid] == 0: Swap arr[mid] and arr[low], increment low and mid.
  • If arr[mid] == 1: Increment mid.
  • If arr[mid] == 2: Swap arr[mid] and arr[high], and decrement high. Crucially, **do not increment mid** because the element swapped from high needs to be checked.

Complexity: Time: O(n). Space: O(1).

Strings & Sliding Window

4. Longest Substring Without Repeating Characters. Medium

Answer & Explanation

Technique: Sliding Window. Use a Hash Set (or a Map) to efficiently track the characters currently present within the window defined by two pointers, left and right.

Process:

  1. Expand the window by moving the right pointer forward and adding s[right] to the set.
  2. If s[right] is already in the set (duplicate found), shrink the window by moving the left pointer forward and removing s[left] from the set until the duplicate is gone.
  3. After every step, update the maximum length found: $max\_len = \max(max\_len, \text{right} - \text{left} + 1)$.

Complexity: Time: O(n). Space: O(min(n, alphabet\_size)).

5. Minimum Window Substring. (Example of a Hard Question) Hard

Answer & Explanation

Technique: Advanced Sliding Window with two Frequency Maps. This uses a "needed" map (for target string T) and a "window" map (for current string S). A crucial variable, formed, tracks how many unique characters in T are matched in the window S.

Process:

  • Expansion: Move the right pointer, updating the window map. Check if the character count now satisfies the need. If so, increment formed.
  • Contraction: Once formed equals the total number of unique characters needed, you have a valid window. Contract the window by moving the left pointer forward until validity is broken. Update the global minimum length during this contraction phase.

Complexity: Time: O(|S| + |T|). Space: O(alphabet\_size).