PROBLEM SOLVING TRICKS - ARRAYS

1-Dimensional Arrays Approaches

1. Two-Pointer Technique

Use Case: When you need to process pairs, remove duplicates, or find subarrays.

Approach: Use two pointers (start & end, or slow & fast) to traverse the array efficiently.

Time Complexity: Typically O(n) - linear time

Examples:

  1. Reverse an array: Swap elements from start and end pointers.
  2. Search an element:
    • Use Linear Search for unsorted arrays (simpler and equally efficient).
    • Use Two-Pointer (Binary Search) only if the array is sorted (O(log n) time).
  3. Remove duplicates: Use a slow pointer to track unique elements.
  4. Two-sum problem: Sort the array and use two pointers to find pairs.

2. Sliding Window Technique

The Sliding Window is an algorithmic technique used to efficiently solve problems involving arrays, strings, or sequences by maintaining a "window" of elements that satisfies certain conditions.

Use Case: For problems involving subarrays with a fixed size or a condition (e.g., maximum sum, smallest subarray).

Approach: Maintain a window (subarray) and adjust its size dynamically.

Performance: Reduces time complexity from O(n²) to O(n) for many problems

Examples:

  1. Maximum sum of k consecutive elements.
  2. Longest subarray with sum ≤ K.
  3. Minimum size subarray with sum ≥ target.

3. Binary Search on Arrays

Use Case: When the array is sorted (or can be sorted) and you need O(log n) search.

Approach: Divide the search space in half repeatedly.

Note: Only works on sorted arrays or arrays that can be sorted

Examples:

  1. Find an element in a sorted array.
  2. Find the first/last occurrence of an element.
  3. Find peak element in mountain array.
  4. Search in rotated sorted array.

4. Cyclic Rotations & Reversals

Use Case: Rotating an array or reversing parts of it.

Approach: Use reversal tricks to rotate in O(1) space.

Space Efficiency: O(1) - constant space

Example:

  1. Rotate array right by k steps
  2. Reverse specific portions of an array
  3. Implement circular buffer operations

5. Frequency Counting (Hashing)

Use Case: When you need to count occurrences or find duplicates.

Approach: Use a hash map (or an array if elements are bounded) to store frequencies.

Trade-off: Uses additional space for faster lookups

Examples:

  1. Find duplicates in an array.
  2. First non-repeating element.
  3. Find all numbers disappeared in an array.
  4. Group anagrams together.

6. Swap & Reorder Techniques

Use Case: When you need to modify the array in-place (e.g., move zeros to end, segregate even-odd numbers).

Approach: Use a pointer to track the correct position and swap elements.

In-place: Modifies array without using significant extra space

Examples:

  1. Move all zeros to the end.
  2. Segregate even and odd numbers.
  3. Dutch national flag problem.
  4. Move all negatives to one side.

7. Prefix Sum (Cumulative Sum)

Use Case: When you need to compute range sums or differences efficiently.

Approach: Precompute cumulative sums to answer range queries in O(1) time.

Efficiency: O(n) pre-processing, O(1) range sum queries

Examples:

  1. Find equilibrium index (where left sum = right sum).
  2. Subarray sum equals K.
  3. Range sum queries on immutable arrays.
  4. Maximum average subarray.

8. Kadane's Algorithm (Maximum Subarray Sum)

Use Case: Finding the maximum sum of a contiguous subarray.

Approach: Keep track of the current sum and reset it if it becomes negative.

Optimal: O(n) time, O(1) space solution

Variations:

  1. Maximum subarray sum (classic problem)
  2. Maximum product subarray
  3. Maximum circular subarray sum
  4. Maximum sum with at most k elements