Scribd
Upload
19 views2 pages

DSA Array Patterns Guide

The document outlines various DSA array patterns including Sliding Window, Two Pointers, and Prefix Sum, each suited for specific types of problems. It highlights algorithms like Kadane's for maximum subarray sums and Binary Search for element location in sorted arrays. Additionally, it covers sorting techniques such as Cyclic Sort and the Dutch National Flag method, along with strategies for merging intervals and using a Monotonic Stack.

Uploaded by

Ashish Kumar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
19 views2 pages

DSA Array Patterns Guide

The document outlines various DSA array patterns including Sliding Window, Two Pointers, and Prefix Sum, each suited for specific types of problems. It highlights algorithms like Kadane's for maximum subarray sums and Binary Search for element location in sorted arrays. Additionally, it covers sorting techniques such as Cyclic Sort and the Dutch National Flag method, along with strategies for merging intervals and using a Monotonic Stack.

Uploaded by

Ashish Kumar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

DSA Array Patterns

1. Sliding Window

Ideal for problems involving subarrays with a fixed or variable size, such as maximum sum subarray

of size k.

2. Two Pointers

Useful in sorted arrays for finding pairs with a specific sum or rearranging elements.

3. Prefix Sum

Helps to compute range sums quickly. Commonly used in problems involving frequent range

queries.

4. Kadane's Algorithm

Efficient algorithm to find the maximum sum subarray in O(n) time.

5. Binary Search

Used to find elements or positions in sorted arrays. Can be extended to search boundaries or peak

elements.

6. Cyclic Sort

Used when the input array contains numbers in a fixed range (e.g., 1 to n). Efficiently sorts with O(1)

space.

7. Dutch National Flag

Useful for sorting arrays with three distinct values, e.g., sorting 0s, 1s, and 2s.

8. Merge Intervals (on Arrays)

Involves sorting and then merging overlapping intervals. Common in meeting schedule problems.

9. Monotonic Stack

Helps solve problems like Next Greater Element, Largest Rectangle in Histogram, etc.

10. Subarray Sum Equals K


Involves using a HashMap to store prefix sums and quickly find the number of subarrays with a

given sum.

You might also like