Array & String Coding Problems — Interview Guide with Solutions
Array and string problems are the most common category in coding interviews, appearing in nearly every technical screen. This guide covers essential patterns and problems with solutions in three languages.
Learning Path
flowchart LR A["Coding Interview Prep"] --> B["Array & String Problems
You are here"] B --> C["Sorting & Searching"] C --> D["System Design Prep"] style B fill:#f90,color:#fff,stroke-width:2px
Two-Pointer Technique
The two-pointer technique uses two indices to traverse an array from opposite ends or at different speeds, reducing time complexity from O(n^2) to O(n).
def two_sum_sorted(nums, target):
left, right = 0, len(nums) - 1
while left < right:
cur = nums[left] + nums[right]
if cur == target:
return [left, right]
elif cur < target:
left += 1
else:
right -= 1
return [-1, -1]
print(two_sum_sorted([2, 7, 11, 15], 9))
print(two_sum_sorted([1, 3, 5, 7], 10))
[0, 1]
[1, 3]
public class TwoSumSorted {
public static int[] twoSum(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) return new int[]{left, right};
else if (sum < target) left++;
else right--;
}
return new int[]{-1, -1};
}
public static void main(String[] args) {
int[] result = twoSum(new int[]{2, 7, 11, 15}, 9);
System.out.println(result[0] + ", " + result[1]);
}
}
0, 1
#include <vector>
#include <iostream>
using namespace std;
vector<int> twoSum(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) return {left, right};
else if (sum < target) left++;
else right--;
}
return {-1, -1};
}
int main() {
vector<int> nums = {2, 7, 11, 15};
auto res = twoSum(nums, 9);
cout << res[0] << ", " << res[1] << endl;
return 0;
}
0, 1
Sliding Window
Use a window that expands and contracts to track a contiguous subarray or substring that satisfies a condition.
def length_of_longest_substring(s):
char_index = {}
start = 0
max_len = 0
for end, ch in enumerate(s):
if ch in char_index and char_index[ch] >= start:
start = char_index[ch] + 1
char_index[ch] = end
max_len = max(max_len, end - start + 1)
return max_len
print(length_of_longest_substring("abcabcbb"))
print(length_of_longest_substring("bbbbb"))
3
1
public class LongestSubstring {
public static int lengthOfLongestSubstring(String s) {
int[] index = new int[128];
int start = 0, maxLen = 0;
for (int end = 0; end < s.length(); end++) {
char ch = s.charAt(end);
start = Math.max(start, index[ch]);
index[ch] = end + 1;
maxLen = Math.max(maxLen, end - start + 1);
}
return maxLen;
}
public static void main(String[] args) {
System.out.println(lengthOfLongestSubstring("abcabcbb"));
}
}
3
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int lengthOfLongestSubstring(string s) {
vector<int> index(128, 0);
int start = 0, maxLen = 0;
for (int end = 0; end < s.size(); end++) {
start = max(start, index[s[end]]);
index[s[end]] = end + 1;
maxLen = max(maxLen, end - start + 1);
}
return maxLen;
}
int main() {
cout << lengthOfLongestSubstring("abcabcbb") << endl;
return 0;
}
3
Prefix Sum
Prefix sums precompute cumulative totals to answer range sum queries in O(1) time.
def subarray_sum(nums, k):
prefix_sum = 0
count = 0
sum_map = {0: 1}
for num in nums:
prefix_sum += num
if prefix_sum - k in sum_map:
count += sum_map[prefix_sum - k]
sum_map[prefix_sum] = sum_map.get(prefix_sum, 0) + 1
return count
print(subarray_sum([1, 1, 1], 2))
print(subarray_sum([1, 2, 3], 3))
2
2
Common Mistakes
- Off-by-one in two-pointer — Using
left <= rightwhenleft < rightis correct for pair-finding. Test with even and odd length arrays. - Forgetting to update Sliding Window state — When the window shrinks, the left character must be removed from tracking.
- Not handling empty strings — Always check
if not sors.length() == 0before accessing characters. - Confusing index with value — Two-sum problems sometimes ask for values, sometimes for indices. Clarify with your interviewer.
- Ignoring character encoding — For Unicode strings, use language-native codepoint APIs instead of byte arrays.
- Mutating input during iteration — Modifying an array while iterating over it causes skipped elements or index errors.
- Hash collision assumptions — Python dict and Java HashMap handle collisions internally, but C++ unordered_map may degrade to O(n) with poor hash functions.
Practice Questions
1. Implement the three-sum problem using the two-pointer technique.
Sort the array first. Fix one element, then use Two Pointers on the remaining subarray. Time: O(n^2), Space: O(log n) for sorting.
2. How would you find the longest palindromic substring?
Expand around each center (both single-character and two-character centers). Track the longest palindrome found. Time: O(n^2), Space: O(1).
3. Challenge: Trapping Rain Water
Given an array of heights, compute how much water can be trapped after rain. Use the two-pointer approach tracking left and right max heights.
def trap(height):
left, right = 0, len(height) - 1
left_max = right_max = water = 0
while left < right:
if height[left] < height[right]:
if height[left] >= left_max:
left_max = height[left]
else:
water += left_max - height[left]
left += 1
else:
if height[right] >= right_max:
right_max = height[right]
else:
water += right_max - height[right]
right -= 1
return water
print(trap([0,1,0,2,1,0,1,3,2,1,2,1]))
6
FAQ
Related Tutorials
Built by the developers of Doda Browser, DodaZIP, and Durga Antivirus Pro. Updated 2026-06-23.
Built by the developers of DodaTech
Doda Browser, DodaZIP & Durga Antivirus Pro