Scribd
Upload
14 views7 pages

? Complete Array Notes

The document provides a comprehensive guide on approaching array-related problems, emphasizing key concepts such as traversal patterns, searching techniques, and various algorithms like Kadane’s and Moore’s Voting. It outlines common problems, patterns for optimization, and a checklist for edge cases to consider before coding. Additionally, it includes a practice plan and common interview questions to aid in preparation.

Uploaded by

uswaasthika3
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
14 views7 pages

? Complete Array Notes

The document provides a comprehensive guide on approaching array-related problems, emphasizing key concepts such as traversal patterns, searching techniques, and various algorithms like Kadane’s and Moore’s Voting. It outlines common problems, patterns for optimization, and a checklist for edge cases to consider before coding. Additionally, it includes a practice plan and common interview questions to aid in preparation.

Uploaded by

uswaasthika3
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

📘 COMPLETE ARRAY NOTES (BEGINNER → LEETCODE MEDIUM)

🧠 0. HOW TO APPROACH ANY ARRAY QUESTION

Before coding, ALWAYS think:

1. ❓ What is asked? (max / count / subarray / pair)

2. 🔍 Constraints? (sorted? negatives? size?)

3. 🧩 Pattern? (two pointer / prefix / sliding window)

4. ⚡ Can I reduce O(n²) → O(n)?

🔹 1. ARRAY BASICS

Key Points

 Fixed size

 Index-based access → O(1)

 Default values:

o int → 0

o boolean → false

Common Problems

 Find max/min

 Sum of elements

 Reverse array

🔹 2. TRAVERSAL PATTERNS

for(int i=0;i<n;i++) {} // forward

for(int i=n-1;i>=0;i--) {} // reverse

for(int x : arr) {} // enhanced loop

👉 Used in almost every problem

🔹 3. SEARCHING
Linear Search → O(n)

Binary Search → O(log n) (ONLY sorted)

int mid = l + (r-l)/2; // avoid overflow

Problems

 Search element

 First/Last occurrence

 Floor/Ceil

🔥 4. TWO POINTER (VERY IMPORTANT)

When to use?

 Sorted array

 Pair problems

 Reverse / in-place

Pattern

int l=0, r=n-1;

while(l<r){

if(condition) l++;

else r--;

Problems

 Two Sum (sorted)

 Move zeroes

 Remove duplicates

 Container with most water

🔥 5. SLIDING WINDOW

Fixed Size

sum += arr[i] - arr[i-k];

Variable Size
while(condition){

l++;

Use When

 Subarray

 Continuous segment

Problems

 Max sum subarray (size K)

 Longest substring

 Minimum window

🔥 6. PREFIX SUM

Idea

Store cumulative sum

prefix[i] = prefix[i-1] + arr[i];

Key Formula

sum(l,r) = prefix[r] - prefix[l-1]

Problems

 Subarray sum = K

 Range sum query

 Equilibrium index

🔥 7. KADANE’S ALGORITHM

Max Subarray

curr = [Link](arr[i], curr + arr[i]);

max = [Link](max, curr);

Use

 Max sum subarray


🔥 8. HASHING (FREQUENCY)

[Link](x, [Link](x,0)+1);

Use

 Counting

 Duplicates

 Majority element

🔥 9. MOORE’S VOTING

👉 Majority element (> n/2)

if(count==0) candidate=x;

count += (x==candidate)?1:-1;

🔥 10. SORTING + ARRAY

[Link](arr);

Use

 Grouping

 Two pointer after sorting

🔥 11. BIT MANIPULATION

res ^= x;

Use

 Single number

 Missing number

🔥 12. ROTATION PATTERN

k = k % n;

reverse(all)

reverse(0,k-1)

reverse(k,n-1)
🔥 13. DUTCH NATIONAL FLAG

low, mid, high

Use

 Sort 0,1,2

🔥 14. SUBARRAY PATTERNS

Type Approach

Sliding
Fixed size
window

Variable Two pointer

With
Prefix sum
negative

🔥 15. COMMON INTERVIEW QUESTIONS

Easy

 Two Sum

 Move Zeroes

 Missing Number

 Majority Element

Medium

 3Sum

 Subarray Sum = K

 Product Except Self

 Sort Colors

 Rotate Array

🧠 16. EDGE CASE CHECKLIST

Before coding:
✔ Empty array
✔ Single element
✔ All same values
✔ Negative numbers
✔ k>n
✔ Overflow

⚠️17. COMMON MISTAKES

❌ Using extra space unnecessarily


❌ Not handling edge cases
❌ Wrong pointer movement
❌ Forgetting sorted condition

18. INTERVIEW EXPLANATION TEMPLATE

Say this:

“I’ll start with brute force.”


“That takes O(n²).”
“Optimizing using ___ pattern.”
“Now it becomes O(n).”

🎯 19. PATTERN IDENTIFICATION SHORTCUT

Keywo
Pattern
rd

Pair Two pointer

Subarra Sliding
y window

Sum =
Prefix sum
K

Majority Moore

Binary
Sorted
search

🔥 20. PRACTICE PLAN


Daily:

 3 Easy

 2 Medium

 1 Revision

You might also like