#arrays

1. Sliding Window

Key Idea: A window (a subarray) of fixed or variable size moves across the array. The window is used to compute a metric (e.g., sum, maximum, minimum) for each position.

Use Case:

Find the maximum sum of a subarray of length k.

Find the longest subarray with sum ≤ k.

Find the minimum window substring that contains all characters of a target string.

Example Problem:

Maximum Sum Subarray of Length k

Input: [1, 4, 2, -1, 3], k = 3

Output: 7 (sum of [1, 4, 2]).

2. Two-Pointer

Key Idea: Use two pointers (e.g., left and right) to traverse the array, often adjusting both pointers to find a solution.

Sorted arrays: Use for pair problems (e.g., two-sum, triplet sum).

Unsorted arrays: Use for problems where you need to find a pair or subarray with a specific condition.

Use Case:

Find the first occurrence of a pair with sum equal to target.

Find the longest subarray with sum equal to k.

Find the maximum product of two numbers in an array.

Example Problem:

Two Sum

Input: [2, 7, 11, 15], target = 9

Output: [0, 1] (indices of 2 and 7).

3. Prefix Sum

Key Idea: Compute the cumulative sum of elements up to each index. This helps quickly calculate the sum of any subarray.

Use Case:

Find the number of subarrays with sum equal to k.

Find the maximum sum of a subarray (Kadane's algorithm).

Find the minimum sum of a subarray.

Example Problem:

Subarray Sum Equals K

Input: [1, 2, 3, 4, 5], k = 6

Output: 2 (subarrays [1,2,3] and [2,4]).

4. Subarray Sum Equals K

Key Idea: Use prefix sums and a hash map to track the number of times a prefix sum has occurred. This allows efficient computation of subarrays with a given sum.

Use Case:

Count the number of subarrays with a specific sum.

Find the longest subarray with sum equal to k.

Example Problem:

Subarray Sum Equals K

Input: [1, 2, 3, 4, 5], k = 6

Output: 2 (subarrays [1,2,3] and [2,4]).

5. Maximum Subarray (Kadane’s Algorithm)

Key Idea: Track the maximum sum of a contiguous subarray by iterating through the array and updating the current and maximum sums.

Use Case:

Find the maximum sum of a subarray in an array of integers.

Example Problem:

Maximum Subarray

Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Output: 6 (subarray [4, -1, 2, 1]).

6. Minimum Window Substring

Key Idea: Use a sliding window to find the smallest subarray that contains all characters of a target string.

Use Case:

Find the minimum window substring containing all characters of a target string.

Example Problem:

Minimum Window Substring

Input: s = "ADOBEC", t = "ABC"

Output: "BEC" (smallest substring containing all characters of "ABC").

7. Two Sum (Unsorted Array)

Key Idea: Use a hash map to store elements and their indices. For each element, check if the complement (target - current) exists in the map.

Use Case:

Find the first pair of indices in an array whose sum equals a target.

Example Problem:

Two Sum

Input: [3, 2, 4], target = 6

Output: [1, 2] (indices of 2 and 4).

8. Longest Increasing Subsequence (LIS)

Key Idea: Track the longest subsequence where elements are in increasing order. This is a classic dynamic programming problem.

Use Case:

Find the length of the longest increasing subsequence in an array.

Example Problem:

Longest Increasing Subsequence

Input: [10, 9, 2, 5, 3, 7, 101, 18]

Output: 4 (e.g., [2, 3, 7, 101]).

9. Find Duplicate

Key Idea: Use a two-pointer approach to find the first duplicate element in an array.

Use Case:

Find the first duplicate in an array (e.g., nums = [1, 3, 4, 2, 2]).

Example Problem:

Find Duplicate

Input: [1, 3, 4, 2, 2]

Output: 2.

10. Find Unique Element

Key Idea: Use XOR (bitwise operation) to find the only unique element in an array where all other elements appear exactly twice.

Use Case:

Find the unique element in an array of integers with all duplicates appearing twice.

Example Problem:

Find Unique Element

Input: [2, 3, 5, 4, 3, 2, 5]

Output: 4.

Bonus: Hash Map for Element Tracking

Key Idea: Use a hash map to store elements and their frequencies for problems like counting duplicates, finding pairs, or tracking occurrences.

Use Case:

Count the frequency of each element in an array.

Find the first occurrence of a duplicate.

How to Recognize These Patterns

Pattern When to Use Example Problem Sliding Window Fixed/variable size window for subarray metrics Maximum sum of a subarray of length k Two-Pointer Pair/substring problems with sorted/unsorted arrays Two Sum, Longest Substring with Equal Characters Prefix Sum Subarray sum problems Subarray Sum Equals K Kadane’s Algorithm Maximum/minimum subarray sum Maximum Subarray Hash Map Tracking element frequencies or pairs Two Sum, Find Duplicate