LeetCode - Binary Search Problems

 

📘 5. LeetCode Problems Using Binary Search

---

✅ Easy

1. 704. Binary Search

Question: Given an array of integers nums which is sorted in ascending order, and an integer target, return the index if the target is found. If not, return -1.

Brute Force:

int search(vector<int>& nums, int target) {
    for (int i = 0; i < nums.size(); ++i)
        if (nums[i] == target) return i;
    return -1;
}

Time Complexity: O(n)

Optimal (Binary Search):

int search(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

Time Complexity: O(log n)

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4

Iteration Table:

Left	Right	Mid	nums[Mid]	Comparison
0	5	2	3	3 < 9 → move right
3	5	4	9	Found!

---

2. 35. Search Insert Position

Question: Given a sorted array and a target value, return the index if found. If not, return the index where it would be if it were inserted in order.

Brute Force:

int searchInsert(vector<int>& nums, int target) {
    for (int i = 0; i < nums.size(); ++i)
        if (nums[i] >= target) return i;
    return nums.size();
}

Time Complexity: O(n)

Optimal (Binary Search):

int searchInsert(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return left;
}

Input: nums = [1,3,5,6], target = 5
Output: 2

Iteration Table:

Left	Right	Mid	nums[Mid]	Comparison
0	3	1	3	3 < 5 → L=2
2	3	2	5	Found

---

3. 278. First Bad Version

Question: Given n versions [1, 2, ..., n] and an API isBadVersion(version) returns whether version is bad. Find the first bad version.

Optimal (Binary Search):

int firstBadVersion(int n) {
    int left = 1, right = n;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (isBadVersion(mid)) right = mid;
        else left = mid + 1;
    }
    return left;
}

Input: n = 5, first bad = 4
Output: 4

Iteration Table:

Left	Right	Mid	isBadVersion	Next
1	5	3	false	left = 4
4	5	4	true	right = 4
Left == Right → Return 4

---

✅ Medium

4. 33. Search in Rotated Sorted Array

Question: Search target in rotated sorted array with distinct elements.

Optimal:

int search(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) return mid;
        if (nums[left] <= nums[mid]) {
            if (nums[left] <= target && target < nums[mid]) right = mid - 1;
            else left = mid + 1;
        } else {
            if (nums[mid] < target && target <= nums[right]) left = mid + 1;
            else right = mid - 1;
        }
    }
    return -1;
}

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

---

5. 162. Find Peak Element

Question: Find index i such that nums[i] > nums[i-1] && nums[i] > nums[i+1].

Optimal:

int findPeakElement(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int mid = (left + right) / 2;
        if (nums[mid] > nums[mid + 1]) right = mid;
        else left = mid + 1;
    }
    return left;
}

Input: nums = [1,2,3,1]
Output: 2

The goal is to find an index i where nums[i] > nums[i-1] && nums[i] > nums[i+1].

---

🔁 Iteration Table:

Iteration	left	right	mid	nums[mid]	nums[mid+1]	Comparison	Action
1	0	3	1	2	3	2 < 3	left = mid+1 (left = 2)
2	2	3	2	3	1	3 > 1	right = mid (right = 2)

🔚 Final State:

left == right == 2 → Return index 2
➡️ Output: 2

This is the peak element satisfying the condition:
nums[2] = 3 > nums[1] = 2 && nums[2] = 3 > nums[3] = 1

6. 153. Find Minimum in Rotated Sorted Array

int findMin(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int mid = (left + right) / 2;
        if (nums[mid] > nums[right]) left = mid + 1;
        else right = mid;
    }
    return nums[left];
}

Input: nums = [3,4,5,1,2]
Output: 1

We want to find the minimum element in the rotated sorted array.

---

🔁 Iteration Table:

Iteration	left	right	mid	nums[mid]	nums[right]	Comparison	Action
1	0	4	2	5	2	5 > 2	left = mid + 1 → 3
2	3	4	3	1	2	1 < 2	right = mid → 3

🔚 Final State:

left == right == 3 → Return nums[3] = 1

➡️ Output: 1

---

7. 34. Find First and Last Position of Element in Sorted Array

vector<int> searchRange(vector<int>& nums, int target) {
    int first = -1, last = -1;
    // First occurrence
    int l = 0, r = nums.size() - 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (nums[mid] >= target) r = mid - 1;
        else l = mid + 1;
        if (nums[mid] == target) first = mid;
    }
    // Last occurrence
    l = 0, r = nums.size() - 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (nums[mid] <= target) l = mid + 1;
        else r = mid - 1;
        if (nums[mid] == target) last = mid;
    }
    return {first, last};
}

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

---

🔍 Step 1: Find First Occurrence

while (l <= r) {
    int mid = (l + r) / 2;
    if (nums[mid] >= target) r = mid - 1;
    else l = mid + 1;
    if (nums[mid] == target) first = mid;
}

Iteration	l	r	mid	nums[mid]	Comparison	Action	first
1	0	5	2	7	7 < 8 → move right	l = mid + 1 → l = 3	-1
2	3	5	4	8	8 >= 8	r = mid - 1 → r = 3	4
3	3	3	3	8	8 >= 8	r = mid - 1 → r = 2	3

✅ first = 3

---

🔍 Step 2: Find Last Occurrence

while (l <= r) {
    int mid = (l + r) / 2;
    if (nums[mid] <= target) l = mid + 1;
    else r = mid - 1;
    if (nums[mid] == target) last = mid;
}

Iteration	l	r	mid	nums[mid]	Comparison	Action	last
1	0	5	2	7	7 < 8 → move right	l = mid + 1 → l = 3	-1
2	3	5	4	8	8 <= 8	l = mid + 1 → l = 5	4
3	5	5	5	10	10 > 8	r = mid - 1 → r = 4	4

✅ last = 4

---

✅ Final Output:

{3, 4}

 

---

✅ Hard

8. 410. Split Array Largest Sum

Question: Split array into k subarrays such that the largest sum among these is minimized.

Optimal (Binary Search on Answer):

bool isValid(vector<int>& nums, int maxSum, int k) {
    int cnt = 1, currSum = 0;
    for (int n : nums) {
        if (currSum + n > maxSum) {
            ++cnt;
            currSum = n;
        } else currSum += n;
    }
    return cnt <= k;
}

int splitArray(vector<int>& nums, int k) {
    int left = *max_element(nums.begin(), nums.end());
    int right = accumulate(nums.begin(), nums.end(), 0);
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (isValid(nums, mid, k)) right = mid;
        else left = mid + 1;
    }
    return left;
}

Input: nums = [7,2,5,10,8], k = 2
Output: 18

---

9. 1231. Divide Chocolate

Question: Like problem 410 but maximize minimum sweetness among k+1 pieces.

bool canDivide(vector<int>& sweetness, int k, int minSweet) {
    int count = 0, curr = 0;
    for (int s : sweetness) {
        curr += s;
        if (curr >= minSweet) {
            count++;
            curr = 0;
        }
    }
    return count >= k + 1;
}

int maximizeSweetness(vector<int>& sweetness, int k) {
    int left = 1, right = accumulate(sweetness.begin(), sweetness.end(), 0);
    while (left < right) {
        int mid = left + (right - left + 1) / 2;
        if (canDivide(sweetness, k, mid)) left = mid;
        else right = mid - 1;
    }
    return left;
}

Input: sweetness = [1,2,3,4,5,6,7,8,9], k = 5
Output: 6

 

Binary Search Basics

🔍 What is Binary Search?

Binary Search is a fast algorithm to search for an element in a sorted array (or range). It repeatedly divides the search space in half, eliminating one half at a time.

---

🧠 When to Use Binary Search?

Use Binary Search when:

✅ The array or list is sorted (ascending or descending)
✅ You want to search quickly (better than linear time)
✅ You're trying to minimize or maximize something (like minimum largest sum, peak element, etc.)

---

⚙️ How Does It Work?

Imagine:

You have a sorted list:
nums = [1, 3, 5, 7, 9, 11, 13]
And you're searching for 9.

Steps:

1. Set two pointers:
   left = 0, right = nums.size() - 1

2. Calculate the middle:
   mid = (left + right) / 2

3. Compare nums[mid] with target:

   • If equal: 🎯 Found it!

   • If nums[mid] < target: Search in right half → left = mid + 1

   • If nums[mid] > target: Search in left half → right = mid - 1

Repeat this loop until left > right.

---

🔄 What’s Happening Internally?

Step	Left	Right	Mid	nums[Mid]	Action
1	0	6	3	7	7 < 9 → Search right
2	4	6	5	11	11 > 9 → Search left
3	4	4	4	9	🎯 Found target

---

🧮 Time and Space Complexity

• Time Complexity: O(log n)

• Space Complexity: O(1) if done iteratively; O(log n) for recursion

---

🛠️ C++ Template Code

int binarySearch(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2; // to avoid overflow
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }

    return -1; // not found
}

---

📦 Use Cases

• Finding a number in a sorted array

• Finding first or last occurrence (modified binary search)

• Solving optimization problems (e.g., minimum days, max sweetness)

• Search space problems where answer lies in a range, not an index

Binary search is an efficient algorithm to find an element in a sorted array.
Time Complexity: O(log n)
Brute-force alternative: Linear search → O(n)

🔧 C++ Binary Search Syntax

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    vector<int> arr = {1, 2, 4, 4, 5, 6, 8, 10};
    int x = 4;

    // 1. binary_search
    bool exists = binary_search(arr.begin(), arr.end(), x);
    cout << "Exists? " << exists << endl;

    // 2. lower_bound
    auto lb = lower_bound(arr.begin(), arr.end(), x);
    cout << "Lower bound of 4: index " << (lb - arr.begin()) << endl;

    // 3. upper_bound
    auto ub = upper_bound(arr.begin(), arr.end(), x);
    cout << "Upper bound of 4: index " << (ub - arr.begin()) << endl;

    return 0;
}

---

🧪 2. Input/Output with Iteration Tables

Given:

arr = {1, 2, 4, 4, 5, 6, 8, 10}
x = 4

✅ Output:

Function	Result	Description
binary_search	true	4 exists
lower_bound	index 2	first index where arr[i] >= 4
upper_bound	index 4	first index where arr[i] > 4

---

📈 3. Binary Search Iteration Table Example

Searching for 4 in {1, 2, 4, 4, 5, 6, 8, 10}

Iteration	low	mid	high	arr[mid]	Action
1	0	3	7	4	Found 4!

Very few steps even in large arrays due to halving.

---

⚙️ 4. Brute Force vs Binary Search (Performance)

Method	Time Complexity	Description
Brute-force	O(n)	Iterate through every element
Binary search	O(log n)	Divide array each iteration

For n = 1e6, brute-force takes ~1 million steps, binary search takes ~20.

---

📘 5. LeetCode Problems Using Binary Search

✅ Easy:

• 704. Binary Search

• 35. Search Insert Position

• 278. First Bad Version

✅ Medium:

• 33. Search in Rotated Sorted Array

• 162. Find Peak Element

• 153. Find Minimum in Rotated Sorted Array

• 34. Find First and Last Position of Element in Sorted Array

✅ Hard:

• 410. Split Array Largest Sum (min/max via BS)

• 1231. Divide Chocolate

---

🔎 6. Min/Max Binary Search (Search Space Binary Search)

Used when you need to minimize/maximize a result.

📌 Problem Example:

875. Koko Eating Bananas

Find the minimum speed k to eat all bananas in h hours.

int minEatingSpeed(vector<int>& piles, int h) {
    int low = 1, high = *max_element(piles.begin(), piles.end());
    while (low < high) {
        int mid = (low + high) / 2;
        int hours = 0;
        for (int pile : piles)
            hours += (pile + mid - 1) / mid;
        if (hours > h)
            low = mid + 1;
        else
            high = mid;
    }
    return low;
}

🧠 You binary search on speed, not index!

---

⚖️ 7. lower_bound() vs upper_bound()

Example:

vector<int> v = {1, 2, 4, 4, 5};

lower_bound(v.begin(), v.end(), 4); // returns iterator to first 4 (index 2)
upper_bound(v.begin(), v.end(), 4); // returns iterator to first element > 4 (index 4)

---

✅ When to Use Which Mechanism?

Problem Type	Use
Find element in sorted array	binary_search
First occurrence (≥ x)	lower_bound
First greater (> x)	upper_bound
Find min/max value satisfying a condition	Custom binary search on range

LeetCode C++ STL

🔁 stack<T> – LIFO (Last-In-First-Out)

✅ Main Methods:

Method	Description
push(value)	Add element on top
pop()	Remove top element
top()	Access top element
empty()	Check if stack is empty
size()	Number of elements

✅ Key Features:

• No iterators or random access

• Built on deque by default

• Only access top

---

🔁 queue<T> – FIFO (First-In-First-Out)

✅ Main Methods:

Method	Description
push(value)	Add element at back
pop()	Remove element from front
front()	Access first element
back()	Access last element
empty()	Check if empty
size()	Get number of elements

✅ Key Features:

• No iterators or random access

• Built on deque

---

🔁 map<Key, Value> – Ordered Map (Red-Black Tree)

✅ Main Methods:

Method	Description
insert({key, value})	Insert a key-value pair
emplace(key, value)	Efficient insert (constructs in-place)
at(key) / operator[]	Access value at key (creates if not exist)
erase(key)	Remove element by key
find(key)	Iterator to key or end() if not found
begin(), end()	Iterators (in key-sorted order)
count(key)	0 or 1 (only unique keys allowed)

✅ Key Features:

• Ordered by key (ascending by default)

• O(log n) insert/find/delete

• No duplicate keys allowed

---

🔁 unordered_map<Key, Value> – Hash Map

✅ Main Methods:

(Same as map, but implemented differently)

Method	Description
insert, emplace, at, operator[], erase, find
begin(), end(), count(key)

✅ Key Features:

• Unordered (no guaranteed key order)

• Hash table based (O(1) average time)

• Faster than map for large datasets (on average)

• No duplicate keys

---

Container	Order	Key Access Time	Duplicate Keys	Usage
stack<T>	N/A	N/A	N/A	LIFO operations
queue<T>	N/A	N/A	N/A	FIFO operations
map<K, V>	Sorted	O(log n)	❌ No	When order matters
unordered_map<K,V>	Unordered	O(1) average	❌ No	When speed matters, not order

---

🔹 vector<T>

✅ Features:

• Dynamic array

• Random access

• O(1) for push_back, amortized

📌 Main Methods:

v.push_back(x);        // Add to end
v.pop_back();          // Remove last
v[i] or v.at(i);       // Access element
v.size();              // Number of elements
v.clear();             // Remove all elements
v.begin(), v.end();    // Iterators

---

🔹 unordered_map<K, V>

✅ Features:

• Hash table

• O(1) average insert, erase, find

• No ordering of keys

📌 Main Methods:

mp[key] = value;       // Insert or update
mp.at(key);            // Access with bounds check
mp.find(key);          // Iterator to key
mp.erase(key);         // Delete key
mp.count(key);         // 0 or 1

---

🔹 map<K, V>

✅ Features:

• Balanced BST (Red-Black Tree)

• Ordered by key

• O(log n) for insert, erase, find

📌 Main Methods:

(Same as unordered_map, but with order)

mp.lower_bound(key);   // ≥ key
mp.upper_bound(key);   // > key

---

🔹 set<T>

✅ Features:

• Ordered unique elements

• O(log n) insert/search

• Sorted order

📌 Main Methods:

s.insert(x);           // Add element
s.erase(x);            // Remove element
s.count(x);            // 0 or 1
s.find(x);             // Iterator

---

🔹 unordered_set<T>

✅ Features:

• Hash table for unique elements

• O(1) average time

• No order

📌 Main Methods:

(Same as set, but unordered)

---

🔹 priority_queue<T> (Max-Heap by default)

✅ Features:

• Automatically keeps largest (or smallest) on top

• Used in heaps, greedy, shortest path

📌 Main Methods:

pq.push(x);            // Add element
pq.top();              // Max (or Min if min-heap)
pq.pop();              // Remove top
pq.empty();            // Check empty

📌 Min Heap:

priority_queue<int, vector<int>, greater<int>> minHeap;

---

🔹 deque<T>

✅ Features:

• Double-ended queue

• O(1) push/pop front and back

• Used in sliding window problems

📌 Main Methods:

dq.push_back(x);       // Add at back
dq.push_front(x);      // Add at front
dq.pop_back();
dq.pop_front();
dq.front(), dq.back();

---

🔹 stack<T>

✅ Features:

• LIFO (Last-In-First-Out)

📌 Main Methods:

s.push(x);
s.pop();
s.top();
s.empty();

---

🔹 queue<T>

✅ Features:

• FIFO (First-In-First-Out)

📌 Main Methods:

q.push(x);
q.pop();
q.front(); q.back();
q.empty();

---

🔹 pair<T1, T2>

✅ Features:

• Hold two related values

📌 Syntax:

pair<int, string> p = {1, "hello"};
p.first; p.second;

---

🔹 tuple<T1, T2, T3,...>

✅ Features:

• Group multiple values

📌 Syntax:

tuple<int, int, string> t = {1, 2, "hi"};
get<0>(t); get<1>(t); get<2>(t);

---

🔹 bitset<N>

✅ Features:

• Fixed-size bit representation

• Great for bitmask DP

📌 Methods:

bitset<8> b("10101010");
b.count();         // Number of 1s
b.any(); b.none();
b.set(i); b.reset(i);
b[i];              // Access bit

LeetCode - Stack - Valid Parentheses/ Next Greater Element/ Next Smaller Element to the Left

---

1. Valid Parentheses

Problem: Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:

• Open brackets are closed by the same type of brackets.

• Open brackets are closed in the correct order.

---

Input:

string s = "({[]})";

Output:

true

---

Brute Force (Less common, but for demonstration: repeated string reduction):

Repeatedly remove pairs "()", "{}", "[]" until no changes:

bool isValidBruteForce(string s) {
    string prev;
    while (s != prev) {
        prev = s;
        s = regex_replace(s, regex("\\(\\)"), "");
        s = regex_replace(s, regex("\\{\\}"), "");
        s = regex_replace(s, regex("\\[\\]"), "");
    }
    return s.empty();
}

Note: This is inefficient, regex not typical in LeetCode C++ solutions.

---

Optimized Stack Approach:

bool isValidOptimized(string s) {
    stack<char> stk;
    for (char c : s) {
        if (c == '(') stk.push(')');
        else if (c == '{') stk.push('}');
        else if (c == '[') stk.push(']');
        else {
            if (stk.empty() || stk.top() != c)
                return false;
            stk.pop();
        }
    }
    return stk.empty();
}

---

Iteration Table:

Iteration	Char	Stack Top after push/pop	Stack content
1	'('	')'	[')']
2	'{'	'}'	[')', '}']
3	'['	']'	[')', '}', ']']
4	']'	(pop ']')	[')', '}']
5	'}'	(pop '}')	[')']
6	')'	(pop ')')	[]

Stack empty → valid.

---

2. Next Greater Element (NGE)

Problem: For each element in array, find the next element greater than it to the right; if none, output -1.

---

Input:

vector<int> nums = {4, 5, 2, 25};

Output:

5 25 25 -1

---

Brute Force: O(n²)

vector<int> nextGreaterBruteForce(vector<int>& nums) {
    int n = nums.size();
    vector<int> result(n, -1);
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            if (nums[j] > nums[i]) {
                result[i] = nums[j];
                break;
            }
        }
    }
    return result;
}

---

Optimized Stack Approach: O(n)

vector<int> nextGreaterOptimized(vector<int>& nums) {
    int n = nums.size();
    vector<int> result(n, -1);
    stack<int> stk;  // stores indices
    
    for (int i = 0; i < n; i++) {
        while (!stk.empty() && nums[i] > nums[stk.top()]) {
            result[stk.top()] = nums[i];
            stk.pop();
        }
        stk.push(i);
    }
    return result;
}

---

Iteration Table:

i	nums[i]	Stack content (indices)	Result updates	Result array
0	4	[0]	-	[-1, -1, -1, -1]
1	5	[] (pop 0)	result[0] = 5	[5, -1, -1, -1]
	push 1
2	2	[1, 2]	-	[5, -1, -1, -1]
3	25	[] (pop 2, pop 1)	result[2] = 25, result[1] = 25	[5, 25, 25, -1]
	push 3

---

3. Monotonic Stack (Next Smaller Element to the Left)

Problem: For each element, find the closest smaller element to the left; if none, output -1.

---

Input:

vector<int> nums = {2, 1, 5, 6, 2, 3};

Output:

-1 -1 1 5 1 2

---

Brute Force: O(n²)

vector<int> nextSmallerLeftBruteForce(vector<int>& nums) {
    int n = nums.size();
    vector<int> result(n, -1);
    for (int i = 0; i < n; i++) {
        for (int j = i-1; j >= 0; j--) {
            if (nums[j] < nums[i]) {
                result[i] = nums[j];
                break;
            }
        }
    }
    return result;
}

---

Optimized Stack Approach: O(n)

vector<int> nextSmallerLeftOptimized(vector<int>& nums) {
    int n = nums.size();
    vector<int> result(n, -1);
    stack<int> stk; // stores elements
    
    for (int i = 0; i < n; i++) {
        while (!stk.empty() && stk.top() >= nums[i]) {
            stk.pop();
        }
        result[i] = stk.empty() ? -1 : stk.top();
        stk.push(nums[i]);
    }
    return result;
}

---

Iteration Table:

i	nums[i]	Stack content (elements)	Result[i]	Action
0	2	[] → push 2	-1	empty stack
1	1	[2] → pop 2, push 1	-1	2 ≥ 1, pop
2	5	[1] → push 5	1	top=1 < 5
3	6	[1,5] → push 6	5	top=5 < 6
4	2	[1,5,6] → pop 6, pop 5, push 2	1	pop until top < 2
5	3	[1,2] → push 3	2	top=2 < 3

---

Summary Table:

Problem	Brute Force Time	Optimized Time	Stack Use
Valid Parentheses	O(n²) (inefficient)	O(n)	Push expected closing
Next Greater Element	O(n²)	O(n)	Monotonic decreasing stack
Next Smaller to Left	O(n²)	O(n)	Monotonic increasing stack

---

LeetCode - unodered_map unordered_set - Frequency Count/ Duplicates Check/ Element Lookups

🧮 1. Frequency Count

Problem: Given an array of integers, return the frequency of each number.

🔹 Input:

nums = {4, 5, 6, 4, 5, 4};

🔹 Output:

4: 3
5: 2
6: 1

---

🔸 Brute Force:

void frequencyBruteForce(vector<int>& nums) {
    for (int i = 0; i < nums.size(); i++) {
        int count = 0;
        for (int j = 0; j < nums.size(); j++) {
            if (nums[i] == nums[j])
                count++;
        }
        cout << nums[i] << ": " << count << endl;
    }
}

🔸 Optimized (unordered_map):

void frequencyOptimized(vector<int>& nums) {
    unordered_map<int, int> freq;
    for (int num : nums) {
        freq[num]++;
    }
    for (auto& [key, value] : freq) {
        cout << key << ": " << value << endl;
    }
}

📊 Iteration Table:

Iteration	num	freq map
1	4	{4: 1}
2	5	{4: 1, 5: 1}
3	6	{4: 1, 5: 1, 6:1}
4	4	{4: 2, 5: 1, 6:1}
5	5	{4: 2, 5: 2, 6:1}
6	4	{4: 3, 5: 2, 6:1}

---

🔁 2. Check Duplicates

Problem: Given an array, check if any element appears more than once.

🔹 Input:

nums = {1, 2, 3, 1};

🔹 Output:

true

---

🔸 Brute Force:

bool hasDuplicateBruteForce(vector<int>& nums) {
    for (int i = 0; i < nums.size(); i++) {
        for (int j = i + 1; j < nums.size(); j++) {
            if (nums[i] == nums[j])
                return true;
        }
    }
    return false;
}

🔸 Optimized (unordered_set):

bool hasDuplicateOptimized(vector<int>& nums) {
    unordered_set<int> seen;
    for (int num : nums) {
        if (seen.count(num))
            return true;
        seen.insert(num);
    }
    return false;
}

📊 Iteration Table:

Iteration	num	seen set	Duplicate Found
1	1	{1}	No
2	2	{1,2}	No
3	3	{1,2,3}	No
4	1	{1,2,3}	Yes ✅

---

🔍 3. Element Lookup

Problem: Check if a given target exists in the array.

🔹 Input:

nums = {10, 20, 30, 40};
target = 30;

🔹 Output:

true

---

🔸 Brute Force:

bool findBruteForce(vector<int>& nums, int target) {
    for (int num : nums) {
        if (num == target)
            return true;
    }
    return false;
}

🔸 Optimized (unordered_set):

bool findOptimized(vector<int>& nums, int target) {
    unordered_set<int> s(nums.begin(), nums.end());
    return s.count(target) > 0;
}

📊 Iteration Table for Building Set:

Iteration	num	set
1	10	{10}
2	20	{10, 20}
3	30	{10, 20, 30}
4	40	{10,20,30,40}

Then:

Lookup: s.count(30) → true ✅

---

Summary

Use Case	Brute Force Time	Optimized Time	Data Structure
Frequency Count	O(n²)	O(n)	unordered_map<int,int>
Duplicates	O(n²)	O(n)	unordered_set<int>
Lookup	O(n)	O(1)	unordered_set<int>

LeetCode - Hash Map / Set - Two Sum/ Contains Duplicates/ Top K Frequent Element

🔷 Problem 1: Two Sum (LeetCode #1)

Find two numbers that add up to the target. Return their indices.

🧾 Input:

nums = [2, 7, 11, 15], target = 9

✅ Output:

[0, 1]  // because 2 + 7 = 9

---

❌ Brute Force (O(n²)):

vector<int> twoSum(vector<int>& nums, int target) {
    for (int i = 0; i < nums.size(); ++i)
        for (int j = i + 1; j < nums.size(); ++j)
            if (nums[i] + nums[j] == target)
                return {i, j};
    return {};
}

---

✅ Optimized with unordered_map (O(n)):

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> map; // value -> index
    for (int i = 0; i < nums.size(); ++i) {
        int complement = target - nums[i];
        if (map.count(complement))
            return {map[complement], i};
        map[nums[i]] = i;
    }
    return {};
}

---

📊 Iteration Table

i	nums[i]	target - nums[i]	map (val → idx)	Action
0	2	7	{}	Store 2 → 0
1	7	2	{2 → 0}	Found! return [0, 1]

---

---

🔷 Problem 2: Contains Duplicate (LeetCode #217)

Return true if any number appears more than once.

🧾 Input:

nums = [1, 2, 3, 1]

✅ Output:

true

---

❌ Brute Force (O(n²)):

bool containsDuplicate(vector<int>& nums) {
    for (int i = 0; i < nums.size(); ++i)
        for (int j = i + 1; j < nums.size(); ++j)
            if (nums[i] == nums[j])
                return true;
    return false;
}

---

✅ Optimized with unordered_set (O(n)):

bool containsDuplicate(vector<int>& nums) {
    unordered_set<int> seen;
    for (int num : nums) {
        if (seen.count(num)) return true;
        seen.insert(num);
    }
    return false;
}

---

📊 Iteration Table

i	nums[i]	seen set	Action
0	1	{}	Insert 1
1	2	{1}	Insert 2
2	3	{1, 2}	Insert 3
3	1	{1, 2, 3}	Found duplicate → true

---

---

🔷 Problem 3: Top K Frequent Elements (LeetCode #347)

Return the k most frequent elements.

🧾 Input:

nums = [1,1,1,2,2,3], k = 2

✅ Output:

[1, 2]

---

❌ Brute Force (O(n²)):

• Count manually using nested loops and sort.

---

✅ Optimized with unordered_map + Min Heap (O(n log k)):

vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> freq;
    for (int n : nums) freq[n]++;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> minHeap;
    for (auto& [num, count] : freq) {
        minHeap.push({count, num});
        if (minHeap.size() > k)
            minHeap.pop();
    }

    vector<int> result;
    while (!minHeap.empty()) {
        result.push_back(minHeap.top().second);
        minHeap.pop();
    }
    return result;
}

---

📊 Iteration Table (frequency map)

num	freq[num]	freq map
1	1	{1:1}
1	2	{1:2}
1	3	{1:3}
2	1	{1:3, 2:1}
2	2	{1:3, 2:2}
3	1	{1:3, 2:2, 3:1}

---

🔚 Summary Table

Problem	Brute Time	Best Time	Structure	STL Container
Two Sum	O(n²)	O(n)	val → index	unordered_map
Contains Duplicate	O(n²)	O(n)	seen check	unordered_set
Top K Frequent Elements	O(n² log n)	O(n log k)	freq count + PQ	unordered_map, heap

---

🔷 Problem 4: Group Anagrams (LeetCode #49)

Group strings that are anagrams of each other.

---

🧾 Input:

strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

✅ Output:

[["eat","tea","ate"],["tan","nat"],["bat"]]

---

❌ Brute Force (O(n² * k log k)):

• Compare every string with every other using sorting.

---

✅ Optimized using unordered_map<string, vector<string>>:

vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string, vector<string>> map;
    for (string& s : strs) {
        string key = s;
        sort(key.begin(), key.end()); // Sorted string as key
        map[key].push_back(s);
    }

    vector<vector<string>> result;
    for (auto& [key, group] : map) {
        result.push_back(group);
    }
    return result;
}

---

📊 Iteration Table

str	Sorted Key	Map (key → list of anagrams)
"eat"	"aet"	{"aet": ["eat"]}
"tea"	"aet"	{"aet": ["eat", "tea"]}
"tan"	"ant"	{"aet": [...], "ant": ["tan"]}
"ate"	"aet"	{"aet": [..., "ate"], "ant": [...]}
"nat"	"ant"	{"aet": [...], "ant": ["tan","nat"]}
"bat"	"abt"	{"...": ..., "abt": ["bat"]}

---

🔷 Problem 5: Subarray Sum Equals K (LeetCode #560)

Count the number of subarrays whose sum equals k.

---

🧾 Input:

nums = [1, 1, 1], k = 2

✅ Output:

2  // Subarrays [1,1] and [1,1]

---

❌ Brute Force (O(n²)):

int subarraySum(vector<int>& nums, int k) {
    int count = 0;
    for (int i = 0; i < nums.size(); i++) {
        int sum = 0;
        for (int j = i; j < nums.size(); j++) {
            sum += nums[j];
            if (sum == k) count++;
        }
    }
    return count;
}

---

✅ Optimized using Prefix Sum + unordered_map<int, int>

int subarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> prefixSum;
    prefixSum[0] = 1;  // base case: sum 0 has 1 occurrence
    int sum = 0, count = 0;

    for (int num : nums) {
        sum += num;
        if (prefixSum.count(sum - k))
            count += prefixSum[sum - k];
        prefixSum[sum]++;
    }
    return count;
}

---

📊 Iteration Table

i	num	sum	sum - k	prefixMap	count
0	1	1	-1	{0:1}	0
1	1	2	0	{0:1,1:1}	1
2	1	3	1	{0:1,1:1,2:1}	2

---

🔷 Problem 6: Longest Consecutive Sequence (LeetCode #128)

1.  ✅ Brute Force — O(n²)

2. ✅ Optimal Solution — O(n) using unordered_set

---

🔴 Problem Statement

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

• You must write an algorithm that runs in O(n) time.

Example:

Input: nums = [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest sequence is [1, 2, 3, 4]

---

🧪 1. Brute Force Approach — O(n²)

✅ Idea:

• For every number x, check if x+1, x+2, ..., exist in the array.

• Use std::find() or loop to check existence.

🔧 Code:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int longestConsecutive(vector<int>& nums) {
    int longest = 0;
    for (int i = 0; i < nums.size(); ++i) {
        int currentNum = nums[i];
        int count = 1;
        
        while (find(nums.begin(), nums.end(), currentNum + 1) != nums.end()) {
            currentNum += 1;
            count += 1;
        }
        
        longest = max(longest, count);
    }
    return longest;
}

🧠 Iteration Example:

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

1. i = 0 → 100 → next = 101 ❌ → count = 1

2. i = 1 → 4 → 5 ❌ → count = 1

3. i = 2 → 200 → 201 ❌ → count = 1

4. i = 3 → 1 → 2 ✅ → 3 ✅ → 4 ✅ → 5 ❌ → count = 4 ✅

5. i = 4 → 3 → 4 ✅ → 5 ❌ → count = 2 ❌

6. i = 5 → 2 → 3 ✅ → 4 ✅ → 5 ❌ → count = 3 ❌

👉 Max count = 4

⛔ Time Complexity: O(n²) because find() is O(n) in a loop

---

✅ 2. Optimal Solution — O(n) using unordered_set

✅ Idea:

1. Insert all numbers into a set (for O(1) lookup).

2. For each number x, check if x-1 exists:

   • If not, it's the start of a sequence.

   • Count how long the sequence goes: x+1, x+2, ...

3. Track the max sequence length.

🔧 Code:

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

int longestConsecutive(vector<int>& nums) {
    unordered_set<int> numSet(nums.begin(), nums.end());
    int longest = 0;

    for (int num : numSet) {
        // Only start counting if it's the start of a sequence
        if (!numSet.count(num - 1)) {
            int currentNum = num;
            int count = 1;

            while (numSet.count(currentNum + 1)) {
                currentNum += 1;
                count += 1;
            }

            longest = max(longest, count);
        }
    }
    return longest;
}

---

🧠 Iteration Example:

Input: [100, 4, 200, 1, 3, 2]
Set = {1, 2, 3, 4, 100, 200}

1. Iteration	num	numSet.count(num - 1)	Is Start of Sequence?	Counted Sequence	count	longest
   1	100	numSet.count(99) = ❌	✅ Yes	100	1	1
   2	4	numSet.count(3) = ✅	❌ No	—	-	1
   3	200	numSet.count(199) = ❌	✅ Yes	200	1	1
   4	1	numSet.count(0) = ❌	✅ Yes	1 → 2 → 3 → 4	4	4
   5	3	numSet.count(2) = ✅	❌ No	—	-	4
   6	2	numSet.count(1) = ✅	❌ No	—	-	4

✅ Max sequence: 4

---

⏱ Time & Space:

• Time: O(n)

• Space: O(n)

---

✅ Final Thoughts

Approach	Time	Space	Use When...
Brute Force	O(n²)	O(1)	Just learning or small inputs
Optimal (Set)	O(n)	O(n)	Required for LeetCode constraints

---

 

LeetCode - Two Pointers - Two Sum II/ Reverse String/ Remove Duplicates from Sorted Array/ Container With Most Water

✅ Problem 1: Two Sum II – Input Array Is Sorted

🔹 Problem:

Given a sorted array of integers numbers and a target, return indices (1-based) of the two numbers such that they add up to the target.

---

🔸 Example:

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

---

🔹 Brute Force (O(n²))

for (int i = 0; i < numbers.size(); i++) {
    for (int j = i + 1; j < numbers.size(); j++) {
        if (numbers[i] + numbers[j] == target)
            return {i + 1, j + 1};
    }
}

i	j	numbers[i]	numbers[j]	sum	sum == 9?
0	1	2	7	9	✅ Yes

---

✅ Optimized: Two Pointers (O(n))

int left = 0, right = numbers.size() - 1;
while (left < right) {
    int sum = numbers[left] + numbers[right];
    if (sum == target) return {left + 1, right + 1};
    else if (sum < target) left++;
    else right--;
}

Left	Right	numbers[left]	numbers[right]	sum	Action
0	3	2	15	17	sum > target → right--
0	2	2	11	13	right--
0	1	2	7	9	✅ Return [1, 2]

---

✅ Problem 2: Reverse String

🔹 Problem:

Reverse the string s in-place.

---

🔸 Brute Force (O(n), but using extra space)

string reversed = "";
for (int i = s.length() - 1; i >= 0; i--) {
    reversed += s[i];
}
s = reversed;

---

✅ Two Pointers (O(n), in-place)

int left = 0, right = s.size() - 1;
while (left < right) {
    swap(s[left++], s[right--]);
}

Example: s = "hello"

Left	Right	s[Left]	s[Right]	After Swap
0	4	h	o	oellh
1	3	e	l	olleh
2	2	l	l	Done

---

✅ Problem 3: Remove Duplicates from Sorted Array

🔹 Problem:

Given a sorted array, remove the duplicates in-place such that each element appears only once and return the new length. Do not allocate extra space.

---

🔹 Input

nums = [0, 0, 1, 1, 1, 2, 2, 3, 4]

---

🔸 Brute Force (❌ Not allowed in interviews for this problem)

vector<int> temp;
for (int i = 0; i < nums.size(); ++i) {
    if (i == 0 || nums[i] != nums[i - 1])
        temp.push_back(nums[i]);
}
nums = temp;
return temp.size();

🧾 Output:

nums = [0, 1, 2, 3, 4]   // New vector
return 5

❌ This uses extra space (temp), which is not allowed by the problem constraints.

---

✅ Two Pointers (In-place, O(n))

int removeDuplicates(vector<int>& nums) {
    if (nums.empty()) return 0;

    int i = 0; // Slow pointer (last unique element index)
    for (int j = 1; j < nums.size(); j++) { // Fast pointer
        if (nums[j] != nums[i]) {
            i++;
            nums[i] = nums[j];
        }
    }
    return i + 1;
}

---

🧾 Input:

nums = [0, 0, 1, 1, 1, 2, 2, 3, 4]

🔁 Iteration Table:

j (fast)	i (slow)	nums[j]	nums[i]	nums (after possible update)
1	0	0	0	[0, 0, 1, 1, 1, 2, 2, 3, 4]
2	0	1	0	[0, 1, 1, 1, 1, 2, 2, 3, 4]
3	1	1	1	[0, 1, 1, 1, 1, 2, 2, 3, 4]
4	1	1	1
5	1	2	1	[0, 1, 2, 1, 1, 2, 2, 3, 4]
6	2	2	2
7	2	3	2	[0, 1, 2, 3, 1, 2, 2, 3, 4]
8	3	4	3	[0, 1, 2, 3, 4, 2, 2, 3, 4]

---

🧾 Output:

nums = [0, 1, 2, 3, 4, _, _, _, _] // After i + 1 = 5
return 5

The contents beyond index 4 can be anything — only the first 5 elements are guaranteed to be the unique sorted elements.

---

💡 Summary

Method	Time Complexity	Space Complexity	In-place?	Return
Brute Force	O(n)	O(n)	❌	New vector
Two Pointers	O(n)	O(1)	✅	Index + 1

---

✅ Problem 4: Container With Most Water

🔹 Problem:

Find the max area of water container formed by two lines in height array.

---

🔸 Brute Force (O(n²))

int maxArea = 0;
for (int i = 0; i < height.size(); i++) {
    for (int j = i + 1; j < height.size(); j++) {
        int area = (j - i) * min(height[i], height[j]);
        maxArea = max(maxArea, area);
    }
}

---

✅ Two Pointers (O(n))

int left = 0, right = height.size() - 1;
int maxArea = 0;
while (left < right) {
    int h = min(height[left], height[right]);
    int w = right - left;
    maxArea = max(maxArea, h * w);
    if (height[left] < height[right]) left++;
    else right--;
}

Example: height = [1,8,6,2,5,4,8,3,7]

Left	Right	height[L]	height[R]	Area	maxArea	Action
0	8	1	7	8	8	left++
1	8	8	7	49	49	right--
1	7	8	3	18	49	right--
1	6	8	8	40	49	right--
1	5	8	4	16	49	right--

.

Java's major new version features

Java's major new version features 

---

✅ Java 8 (2014) — "Functional Java Begins"

🔹 Lambda Expressions

List<String> names = List.of("Sam", "John");
names.forEach(name -> System.out.println("Hi " + name));

Why: Shorter anonymous functions
Real-life: Like sticky notes you don't name.

---

🔹 Streams API

List<String> filtered = names.stream()
                             .filter(name -> name.startsWith("S"))
                             .collect(Collectors.toList());

Why: Clean way to filter, map, reduce
Real-life: Conveyor belt with filters.

---

🔹 Default Methods in Interfaces

interface Animal {
    default void walk() { System.out.println("Walking..."); }
}

Why: Add features without breaking old code

---

✅ Java 9 (2017) — "Modular Java"

🔹 Modules

module com.myapp {
    requires java.base;
}

Why: Better packaging, faster startup
Real-life: Like having labeled suitcases in a large trip.

---

🔹 JShell (REPL)

jshell> int x = 5;
jshell> System.out.println(x * 2);

Why: Quick experiments
Real-life: Like testing a spice while cooking.

---

✅ Java 10 (2018) — "Type Inference"

🔹 var keyword

var list = new ArrayList<String>();

Why: Less boilerplate
Real-life: Like saying “that guy” instead of their full name when context is obvious.

---

✅ Java 11 (2018) — "Polishing Java 8–10"

🔹 var in Lambda Parameters

list.forEach((var name) -> System.out.println(name));

---

🔹 New HTTP Client API

HttpClient client = HttpClient.newHttpClient();

Why: Modern, async-friendly HTTP

---

🔹 Run Java Files without Compilation

java Hello.java

Why: Script-like convenience

---

✅ Java 12–14 — "Small but Useful"

🔹 Switch Expressions (Preview in 12, Stable in 14)

String result = switch(day) {
    case MONDAY -> "Start";
    case FRIDAY -> "Party";
    default -> "Meh";
};

Why: Cleaner switch statements
Real-life: Like a fast menu selection.

---

✅ Java 15 — "Text Blocks"

🔹 Multiline Strings

String json = """
              {
                "name": "ChatGPT",
                "type": "AI"
              }
              """;

Why: Write clean JSON, XML, SQL
Real-life: Copy-pasting real code blocks directly.

---

✅ Java 16–17 — "Records & Pattern Matching"

🔹 record Classes

record User(String name, int age) {}

Why: Auto-generates equals(), hashCode(), etc.
Real-life: Like filling a short form that becomes a full passport.

---

🔹 Pattern Matching for instanceof

if (obj instanceof String s) {
    System.out.println(s.length());
}

---

✅ Java 18 — "UTF-8 & Simpler APIs"

🔹 Default Charset is UTF-8

Why: Consistency across systems

---

✅ Java 19–20 — "Preview of the Future"

🔹 Virtual Threads (Preview)

Thread.startVirtualThread(() -> {
    System.out.println("Hello from virtual thread!");
});

Why: Lightweight threads for massive concurrency
Real-life: Like spawning 1,000 chat bots instead of 1,000 humans.

---

✅ Java 21 (LTS – 2023) — "Power Features Go Mainstream"

🔹 Virtual Threads (Stable)

try (var executor = Executors.newVirtualThreadPerTaskExecutor()) {
    executor.submit(() -> System.out.println("Hello virtual!"));
}

---

🔹 Record Patterns

record Point(int x, int y) {}
Object obj = new Point(1, 2);

if (obj instanceof Point(int x, int y)) {
    System.out.println(x + y);
}

---

🔹 Pattern Matching in switch

switch (obj) {
    case String s -> System.out.println("String: " + s);
    case Integer i -> System.out.println("Int: " + i);
    default -> System.out.println("Unknown");
}

---

🔚 Summary Table

Version	Key Features	Real-Life Analogy
Java 8	Lambdas, Streams, Default methods	Express lanes and personal assistants
Java 9	Modules, JShell	Organized luggage, quick tests
Java 10	var	Letting the system guess simple types
Java 11	HTTP client, Java file execution	No compile step, faster HTTP
Java 14	Switch expressions	Modern fast-food style selection
Java 15	Text blocks	Pasting whole paragraphs cleanly
Java 17	Records, Pattern Matching	Shortcuts for boilerplate data classes
Java 21	Virtual threads, Record patterns	Billions of efficient AI threads

---

Leet Code - Sliding Window - Maximum Number of Vowels in a Substring of Given Length

🧩 Problem: Maximum Number of Vowels in a Substring of Given Length

---

📝 Problem Description:

Given a string s and an integer k, find the maximum number of vowels in any substring of s with length k.

Vowels = {a, e, i, o, u} (case-sensitive: assume lowercase)

---

1️⃣ Brute-force Approach (Naive)

---

🔍 Idea:

• Check every substring of length k

• Count vowels in each substring

• Keep track of the max count

---

🧑‍💻 Code:

bool isVowel(char c) {
    return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}

int maxVowels(string s, int k) {
    int maxCount = 0;
    int n = s.size();
    
    for (int i = 0; i <= n - k; i++) {
        int count = 0;
        for (int j = i; j < i + k; j++) {
            if (isVowel(s[j])) {
                count++;
            }
        }
        maxCount = max(maxCount, count);
    }
    
    return maxCount;
}

---

⏳ Time Complexity:

• Outer loop: runs n-k+1 times → ~O(n)

• Inner loop: runs k times for each outer loop iteration

• Total: O(n * k)

💾 Space Complexity:

• Just some counters and booleans → O(1)

---

🔍 Step-by-step for s = "abciiidef", k = 3

i	Substring	Vowels in substring	maxCount updates to
0	"abc"	a = 1	1
1	"bci"	i = 1	1
2	"cii"	i, i = 2	2
3	"iii"	i, i, i = 3	3
4	"iid"	i, i = 2	3
5	"ide"	i, e = 2	3
6	"def"	e = 1	3

---

2️⃣ Sliding Window Approach (Optimal)

---

🔍 Idea:

• Use a window of size k

• Slide it from left to right

• Add new char at right, remove old char at left from count if vowel

• Track max count along the way

---

🧑‍💻 Code:

int maxVowels(string s, int k) {
    int maxCount = 0, count = 0;
    int n = s.size();
    
    for (int i = 0; i < k; i++) {
        if (isVowel(s[i])) count++;
    }
    maxCount = count;

    for (int i = k; i < n; i++) {
        if (isVowel(s[i])) count++;            // Add right char
        if (isVowel(s[i - k])) count--;        // Remove left char
        maxCount = max(maxCount, count);
    }
    
    return maxCount;
}

---

⏳ Time Complexity:

• We do one pass → O(n)

💾 Space Complexity:

• Only counters → O(1)

---

🔍 Step-by-step for s = "abciiidef", k = 3

Iteration (i)	Window	Count Change	count	maxCount
Initial (0-2)	"abc"	a is vowel → count = 1	1	1
3	"bci" → "cii"	Remove b(not vowel), add i(vowel) → count=2	2	2
4	"cii" → "iii"	Remove c(not vowel), add i(vowel) → count=3	3	3
5	"iii" → "iid"	Remove i(vowel), add d(not vowel) → count=2	2	3
6	"iid" → "ide"	Remove i(vowel), add e(vowel) → count=2	2	3
7	"ide" → "def"	Remove i(vowel), add f(not vowel) → count=1	1	3

---

🔥 Summary:

Approach	Time Complexity	Space Complexity	Explanation
Brute Force	O(n * k)	O(1)	Count vowels every window
Sliding Window	O(n)	O(1)	Update counts by adding/removing 1

---

Leet Code - Sliding Window - Maximum Average Subarray I

---

🔶 Problem: Maximum Average Subarray I

📝 Description:

Given an integer array nums and an integer k, find the contiguous subarray of length k that has the maximum average value, and return this value.

---

📥 Example:

Input: nums = [1,12,-5,-6,50,3], k = 4  
Output: 12.75  
Explanation: Maximum average subarray is [12,-5,-6,50] with average = (12−5−6+50)/4 = 12.75

---

🚫 Brute-force Approach (Bad Way)

❌ Time Complexity: O(n * k)

We calculate the average of every subarray of size k.

double findMaxAverage(vector<int>& nums, int k) {
    double maxAvg = INT_MIN;
    for (int i = 0; i <= nums.size() - k; i++) {
        double sum = 0;
        for (int j = i; j < i + k; j++) {
            sum += nums[j];
        }
        maxAvg = max(maxAvg, sum / k);
    }
    return maxAvg;
}

🔁 Outer loop runs for:
i = 0 to nums.size() - k = 6 - 4 = 2
So it runs for i = 0, 1, 2.
🧠 Iteration-by-iteration Breakdown:
▶️ i = 0
j = 0 to 3
sum = nums[0] + nums[1] + nums[2] + nums[3]
    = 1 + 12 + (-5) + (-6) = 2
avg = 2 / 4 = 0.5
maxAvg = max(INT_MIN, 0.5) = 0.5

▶️ i = 1
j = 1 to 4
sum = 12 + (-5) + (-6) + 50 = 51
avg = 51 / 4 = 12.75
maxAvg = max(0.5, 12.75) = 12.75
▶️ i = 2
j = 2 to 5
sum = -5 + (-6) + 50 + 3 = 42
avg = 42 / 4 = 10.5
maxAvg = max(12.75, 10.5) = 12.75

✅ Final Result:
return maxAvg = 12.75
📋 Summary Table:




i
Subarray
Sum
Average
maxAvg Update




0
[1, 12, -5, -6]
2
0.5
0.5


1
[12, -5, -6, 50]
51
12.75
12.75 (updated)


2
[-5, -6, 50, 3]
42
10.5
12.75 (unchanged)


❌ Why it's bad:

• You recalculate the same numbers multiple times.

• Too slow for large arrays.

---

✅ Optimal Sliding Window Approach (Best Way)

⏱ Time: O(n) — each element added/removed once

💾 Space: O(1) — no extra data structure needed

double findMaxAverage(vector<int>& nums, int k) {
    int windowSum = 0;
    
    // Sum of first window
    for (int i = 0; i < k; i++) {
        windowSum = windowSum + nums[i];
    }

    int maxSum = windowSum;

    for (int i = k; i < nums.size(); i++) {
        windowSum = windowSum + nums[i] - nums[i - k]; // Slide the window
        maxSum = max(maxSum, windowSum);
    }

    return static_cast<double>(maxSum) / k;
}

---

🧠 Step-by-step (for input [1,12,-5,-6,50,3], k = 4):

Initialization:

• windowSum = 1 + 12 + (-5) + (-6) = 2

• maxSum = 2

Iteration:

1. i = 4: Add 50, remove 1
   → windowSum = 2 + 50 - 1 = 51
   → maxSum = 51

2. i = 5: Add 3, remove 12
   → windowSum = 51 + 3 - 12 = 42
   → maxSum = 51

Final:

• Max sum = 51

• Max average = 51 / 4 = 12.75

---

🔍 With/Without Data Structures?

• ❌ No need for a queue, deque, map, etc.

• ✔️ You just track the running window sum → simplest and fastest.

---

✅ Summary

Approach	Time	Space	Notes
Brute-force	O(n * k)	O(1)	Repeats work — not optimal
✅ Sliding window	O(n)	O(1)	Best way — clean and fast

---

 

Leet Code - Sliding Window - maximum sum of a subarray of size k

 

---

Sliding Window Technique 

---

What is Sliding Window?

Sliding window is a way to process a subset (window) of elements in an array or string efficiently by moving the window step-by-step, instead of recalculating everything every time.

---

Example Problem:

Find the maximum sum of a subarray of size k

Given:
nums = [2, 1, 5, 1, 3, 2], and k = 3 (window size)

Goal: Find the maximum sum of any consecutive 3 elements.

---

Step-by-step C++ code:

#include <iostream>
#include <vector>
using namespace std;

int maxSumSubarray(vector<int>& nums, int k) {
    int windowSum = 0, maxSum = 0;
    int windowStart = 0;

    // Loop through each element to slide the window
    for (int windowEnd = 0; windowEnd < nums.size(); windowEnd++) {
        windowSum += nums[windowEnd];  // Add the next element into the window

        // When we hit size k, start sliding the window
        if (windowEnd >= k - 1) {
            maxSum = max(maxSum, windowSum);    // Update maxSum if needed
            windowSum -= nums[windowStart];     // Remove the element going out of the window
            windowStart++;                       // Slide the window forward
        }
    }
    return maxSum;
}

int main() {
    vector<int> nums = {2, 1, 5, 1, 3, 2};
    int k = 3;
    cout << "Maximum sum of subarray of size " << k << " is " << maxSumSubarray(nums, k) << endl;
    return 0;
}

---

What happens in each iteration? (Detailed):

Iteration (windowEnd)	windowSum (after adding nums[windowEnd])	windowStart	maxSum update?	windowSum after sliding	Notes
0	2	0	No	—	Window size < k (1 < 3)
1	2 + 1 = 3	0	No	—	Window size < k (2 < 3)
2	3 + 5 = 8	0	Yes (maxSum=8)	8 - 2 = 6	Window size = k (3)
3	6 + 1 = 7	1	No (maxSum=8)	7 - 1 = 6	Slide window by removing nums[0]=2
4	6 + 3 = 9	2	Yes (maxSum=9)	9 - 5 = 4	Slide window by removing nums[1]=1
5	4 + 2 = 6	3	No (maxSum=9)	6 - 1 = 5	Slide window by removing nums[2]=5

---

Explanation Summary:

• We keep adding elements to windowSum until the window reaches size k.

• Once the window size is k, we compare and update maxSum.

• Then slide the window forward:

  • Remove the element at windowStart from the sum.

  • Increment windowStart to shrink the window from the left.

• Repeat until the end.

 Time and Space Complexity

• Time Complexity: O(n)
  ✔️ Each element is added and removed from windowSum once — very efficient.

• Space Complexity: O(1)
  ✔️ Uses only a few integer variables (no extra arrays or data structures).

Can We Do Better?

Short answer: No — not for this specific problem.

What is Space Complexity?

🧠 What is Space Complexity?

Space complexity is the amount of extra memory your algorithm uses relative to the input size.

It includes:

• Variables

• Data structures (arrays, maps, sets, etc.)

• Function call stack (for recursion)

🔸 Note: Input itself is not counted — only extra space your code uses.

---

🛠 How to Decide Space Complexity (Step by Step)

Let’s break it down:

✅ Step 1: Look at your variables

• Constants → O(1)

• Arrays, vectors, etc. → O(n) if you create one of size n

• 2D arrays → O(n²)

✅ Step 2: Check loops or recursion

• If recursion goes n levels deep → O(n) stack space

• Storing recursive results? Add that too.

✅ Step 3: Check data structures

• vector<int> v(n) → O(n)

• unordered_map<char, int> storing up to 26 keys → O(1)

• But if map size grows with input → O(n)

---

🔎 Example 1: Brute-force Max Avg Subarray

double findMaxAverage(vector<int>& nums, int k) {
    double maxAvg = INT_MIN;
    for (int i = 0; i <= nums.size() - k; i++) {
        double sum = 0;
        for (int j = i; j < i + k; j++) {
            sum += nums[j];
        }
        maxAvg = max(maxAvg, sum / k);
    }
    return maxAvg;
}

✅ Space Analysis:

• maxAvg and sum are scalars → O(1)

• No extra array or recursion

• ➤ Space Complexity: O(1)

---

🔎 Example 2: Using HashMap

unordered_map<char, int> freq;
for (char c : s) {
    freq[c]++;
}

If input string s has all lowercase letters:

• Max 26 keys → still O(1)
  But if input allows Unicode / no size limit:

• Could grow with input size → O(n)

---

🔎 Example 3: Recursive Fibonacci

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

❌ Space: O(n) stack (recursive calls)

---

🧪 Rule of Thumb

Code Feature	Space Complexity
Constant variables	O(1)
Array of size n	O(n)
2D array of n x m	O(n * m)
Recursion to depth n	O(n) stack
Hash map storing n items	O(n)
Sliding window (sum only)	O(1)

---