Scribd
Upload
7 views4 pages

A2Z Array Revision Notes

The document outlines a collection of 40 problems related to arrays, categorized into easy, medium, and hard levels, with both brute force and optimal strategies provided for each problem. It includes techniques such as two-pointer methods, sliding windows, and hashmaps to achieve efficient solutions. The document serves as a quick revision guide for common array manipulation problems and their respective time complexities.

Uploaded by

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

A2Z Array Revision Notes

The document outlines a collection of 40 problems related to arrays, categorized into easy, medium, and hard levels, with both brute force and optimal strategies provided for each problem. It includes techniques such as two-pointer methods, sliding windows, and hashmaps to achieve efficient solutions. The document serves as a quick revision guide for common array manipulation problems and their respective time complexities.

Uploaded by

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

A2Z DSA Sheet – Arrays (40 Problems)

Quick Revision Notes


🔁 Brute to Optimal Strategy | Divided into Easy, Medium, Hard

Easy Level

Largest Element in Array


Brute: Traverse array, track max.
Optimal: Same – O(n).

Second Largest Element (no sort)


Brute: Sort & pick second largest.
Optimal: One pass – track max and second max.

Check if Array is Sorted


Brute: Compare each pair.
Optimal: One pass comparison – O(n).

Remove Duplicates from Sorted Array


Two-pointer – O(n), in-place overwrite.

Left Rotate by 1
Store first, shift rest left, place first at end.

Left Rotate by D
Reverse parts + whole: 3 reversals – O(n).

Move Zeros to End


Two-pointer: one for insert position.

Linear Search
Simple traversal – O(n).

Find Union of Two Arrays


Use Set for union – O(n + m).

Find Missing Number


Sum formula or XOR – O(n).
Max Consecutive Ones
Track current streak, update max – O(n).

Number Appears Once


XOR all – O(n).

Longest Subarray with Sum K (+ve)


Sliding window – O(n).

Longest Subarray with Sum K (+/-)


Prefix sum + HashMap – O(n).

Medium Level

2Sum Problem
HashMap for complement – O(n).

Sort 0s, 1s, 2s


Dutch National Flag algo – O(n).

Majority Element (>n/2)


Boyer-Moore Voting – O(n).

Kadane's Algorithm
Track curr/max sum – O(n).

Print Max Subarray


Track start/end with Kadane.

Stock Buy/Sell
Track min so far, update profit.

Rearrange +ve/-ve
Extra space O(n) or in-place with two pointers.

Next Permutation
Find dip, swap with just larger, reverse rest.

Leaders in Array
Traverse from right, keep max – O(n).

Longest Consecutive Sequence


Set + check starts – O(n).
Set Matrix Zeros
Mark rows/cols, second pass zero them.

Rotate Matrix 90°


Transpose + reverse rows – O(n²).

Spiral Matrix
Traverse layer by layer – O(n*m).

Count Subarrays with Sum


Prefix sum + hashmap – O(n).

Hard Level

Pascal's Triangle
Build row by row using prev row.

Majority Element > n/3


Extended Boyer-Moore – track 2 candidates.

3-Sum
Sort + 2 pointer – O(n²).

4-Sum
Sort + 2 pointer + loop – O(n³).

Largest Subarray with 0 Sum


Prefix sum + hashmap – O(n).

Subarrays with XOR K


Prefix XOR + map – O(n).

Merge Overlapping Intervals


Sort by start, merge – O(n log n).

Merge Sorted Arrays (no extra)


Gap method – O((n+m) log(n+m)).

Repeating & Missing Number


Math (Sum & Square sum) or XOR.

Count Inversions
Modified merge sort – O(n log n).
Reverse Pairs
Merge sort variant – O(n log n).

Max Product Subarray


Track max/min till now – O(n).

You might also like