Array Algorithms & Techniques
Understanding core algorithms and patterns is essential for solving array problems efficiently. This page covers searching algorithms and two widely-used techniques that come up constantly in interviews.
Linear Search
The simplest searching algorithm. We traverse the array sequentially and check each element.
- Analogy: Looking for a specific book on an unsorted shelf. You have to check every single book until you find it or reach the end.
int linearSearch(int arr[], int n, int x)
{
for (int i = 0; i < n; i++)
if (arr[i] == x)
return i; // Return index if found
return -1; // Return -1 if not found
}- Time Complexity: O(N) — scans the entire array in worst case
- Space Complexity: O(1)
- When to use: Unsorted data, small arrays, or when you need to find all occurrences
Binary Search
A much faster searching algorithm for sorted arrays. It works by repeatedly dividing the search interval in half.
- Analogy: Looking for a word in a dictionary. You open the middle, see if the word is earlier or later alphabetically, and repeat on that half.
Crucial Condition: Binary Search only works on sorted arrays. If the array is unsorted, you must sort it first or use Linear Search.
int binarySearch(int arr[], int l, int r, int x)
{
while (l <= r) {
int m = l + (r - l) / 2;
// Check if x is present at mid
if (arr[m] == x)
return m;
// If x greater, ignore left half
if (arr[m] < x)
l = m + 1;
// If x is smaller, ignore right half
else
r = m - 1;
}
// If we reach here, then element was not present
return -1;
}- Time Complexity: O(log N) — much faster than O(N) for large arrays!
- Space Complexity: O(1)
- When to use: Sorted arrays, or problems where you can define a monotonic search condition
Common bug: Using (l + r) / 2 for the midpoint can cause integer
overflow when l and r are large. Always use l + (r - l) / 2 instead.
Two Pointer Technique
The Two Pointer technique uses two indices that move through the array, usually from opposite ends or at different speeds. It converts many O(n^2) problems into O(n).
- Analogy: Two people searching a library shelf from opposite ends, moving toward each other until they meet.
When to use Two Pointers:
- Finding pairs that satisfy a condition (e.g., two numbers that sum to a target)
- Removing duplicates from a sorted array
- Reversing an array in-place
- Partitioning arrays (like in quicksort)
Example: Find a pair with given sum in a sorted array
In this example the pair was found in the first step, but typically the pointers walk inward:
- If
sum < target: move left pointer right (need a larger number) - If
sum > target: move right pointer left (need a smaller number) - If
sum == target: found it!
// Find two numbers in a sorted array that add up to target
pair<int, int> twoSumSorted(int arr[], int n, int target) {
int left = 0, right = n - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target)
return {left, right};
else if (sum < target)
left++; // Need larger sum
else
right--; // Need smaller sum
}
return {-1, -1}; // No pair found
}- Time Complexity: O(N) — each pointer moves at most N times
- Space Complexity: O(1)
Example: Remove duplicates from sorted array (in-place)
// Returns new length with duplicates removed
int removeDuplicates(int arr[], int n) {
if (n == 0) return 0;
int writeIdx = 1; // Slow pointer (where to write next unique)
for (int readIdx = 1; readIdx < n; readIdx++) { // Fast pointer
if (arr[readIdx] != arr[readIdx - 1]) {
arr[writeIdx] = arr[readIdx];
writeIdx++;
}
}
return writeIdx; // New length
}
// Input: [1, 1, 2, 2, 3, 4, 4, 5]
// Output: [1, 2, 3, 4, 5, ...] length = 5Sliding Window Technique
The Sliding Window maintains a “window” (subarray) that slides across the array. Instead of recalculating everything for each position, you add the new element and remove the old one.
- Analogy: Looking through a train window at scenery passing by. The window frame stays the same size, but the view changes as you move.
When to use Sliding Window:
- Maximum/minimum sum subarray of size k
- Longest substring with certain property
- Counting subarrays satisfying a condition
Example: Maximum sum of subarray of size k
Without sliding window, you’d compute the sum from scratch for each position: O(n*k). With sliding window, you update the sum incrementally: O(n).
int maxSumSubarray(int arr[], int n, int k) {
// Compute sum of first window
int windowSum = 0;
for (int i = 0; i < k; i++)
windowSum += arr[i];
int maxSum = windowSum;
// Slide the window: add next element, remove first element
for (int i = k; i < n; i++) {
windowSum += arr[i] - arr[i - k];
maxSum = max(maxSum, windowSum);
}
return maxSum;
}
// arr = {2, 1, 5, 1, 3, 2}, k = 3
// Windows: [2,1,5]=8, [1,5,1]=7, [5,1,3]=9, [1,3,2]=6
// Answer: 9- Time Complexity: O(N) — single pass through the array
- Space Complexity: O(1)
Choosing the Right Technique
| Problem Pattern | Technique | Example |
|---|---|---|
| Find element in unsorted array | Linear Search | ”Is 42 in this array?” |
| Find element in sorted array | Binary Search | ”Find position of 42 in sorted array” |
| Pair with target sum (sorted) | Two Pointers | ”Two numbers that add to 10” |
| Subarray of fixed size | Sliding Window | ”Max sum of 3 consecutive elements” |
| In-place rearrangement | Two Pointers | ”Remove duplicates”, “Partition” |
| Search with a condition | Binary Search | ”First element >= 50” |
Pro Tip: Many problems can be solved with multiple techniques. The key is recognizing which one gives you the best time complexity. When in doubt: sort first if you need Binary Search or Two Pointers; use Sliding Window for subarray problems with a size constraint.