Dutch National Flag (DNF) Sorting Algorithm -

Sorting 0s, 1s, and 2s

Introduction
The Dutch National Flag Algorithm is an efficient way to sort an array containing only 0s, 1s,
and 2s. This problem appears in coding interviews and is also known as Leetcode 75 - Sort
Colors. The algorithm uses three pointers (low, mid, high) to partition and sort the array in a
single pass, achieving a time complexity of O(n) and space complexity of O(1).
Brute Force Approach
A simple way to sort the array is to use built-in sorting algorithms like std::sort():
sort([Link](), [Link]());
Time Complexity: O(n log n) (due to sorting)
Counting Sort Approach
We count the occurrences of 0s, 1s, and 2s, then reconstruct the array.
#include <bits/stdc++.h>
using namespace std;

void countingSort(vector<int>& nums) {

int count0 = 0, count1 = 0, count2 = 0;
for (int num : nums) {
if (num == 0) count0++;
else if (num == 1) count1++;
else count2++;
}
int index = 0;
while (count0--) nums[index++] = 0;
while (count1--) nums[index++] = 1;
while (count2--) nums[index++] = 2;
}
Time Complexity: O(n)
Space Complexity: O(1)
Dutch National Flag Algorithm (Optimal Approach)
This method efficiently sorts the array in a single pass using three pointers: low, mid, high.
Algorithm Explanation:
1. low: Points to the boundary for placing 0s.
2. mid: Iterates through the array.
3. high: Points to the boundary for placing 2s.
4. If nums[mid] == 0, swap it with nums[low] and increment both low and mid.
5. If nums[mid] == 1, just move mid ahead.
6. If nums[mid] == 2, swap it with nums[high] and decrement high.
Implementation in C++:
#include <bits/stdc++.h>
using namespace std;

void dnfSort(vector<int>& nums) {

1 BBN
 int low = 0, mid = 0, high = [Link]() - 1;
while (mid <= high) {
if (nums[mid] == 0) {
swap(nums[low], nums[mid]);
low++, mid++;
} else if (nums[mid] == 1) {
mid++;
} else {
swap(nums[mid], nums[high]);
high--;
}
}
}

Dry Run Example:

Input:
nums = [2, 0, 2, 1, 1, 0]
Step-by-step execution:
Step low mid high nums
1 0 0 5 [2, 0, 2, 1, 1, 0]
2 0 0 4 [0, 0, 2, 1, 1, 2]
3 1 1 4 [0, 0, 2, 1, 1, 2]
4 1 2 4 [0, 0, 1, 2, 1, 2]
5 2 3 4 [0, 0, 1, 1, 2, 2]
6 2 4 4 [0, 0, 1, 1, 2, 2]
Output:
[0, 0, 1, 1, 2, 2]
Time & Space Complexity
 Time Complexity: O(n) (as we traverse the array once)
 Space Complexity: O(1) (only a few extra variables used)

C++ Standard Template Library (STL)

Introduction to STL

 STL provides essential data structures and algorithms to enhance coding

efficiency.
 Useful in coding tests and competitions.
 Contains four key components:
1. Containers (Dynamic Containers: Vectors, Lists, Deques, etc.)
2. Algorithms (Sorting, Searching, etc.)
3. Iterators (Pointer-like objects to navigate containers)

2 BBN
 4. Function Objects

Vectors

 Dynamic array that resizes automatically.

 Advantages over arrays:
o No need to specify size in advance.
o Provides built-in functions for manipulation.

Vector Operations

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

int main() {
vector<int> v = {1, 2, 3, 4, 5};
v.push_back(6); // Add element at end
v.pop_back(); // Remove last element
cout << "First element: " << [Link]() << endl;
cout << "Last element: " << [Link]() << endl;
cout << "Size: " << [Link]() << endl;
return 0;
}

Insertion & Deletion

[Link]([Link]() + 2, 10); // Insert 10 at index 2

[Link]([Link]()); // Remove first element
[Link](); // Remove all elements

Iterators in Vectors

vector<int>::iterator it = [Link]();
cout << *it; // Access first element using iterator

Lists (Doubly Linked List)

 Allows insertion and deletion from both ends efficiently.

List Operations
#include <iostream>
#include <list>
using namespace std;

int main() {
list<int> l = {10, 20, 30};
l.push_front(5);
l.push_back(40);

3 BBN
 l.pop_front();
l.pop_back();
return 0;
}

Deque (Double-Ended Queue)

 Allows push/pop from both front and back efficiently.

Deque Example

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

int main() {
deque<int> dq;
dq.push_front(1);
dq.push_back(2);
dq.pop_front();
return 0;
}

Pairs

 Stores two values together.

Pair Example
pair<int, string> p = {1, "hello"};
cout << [Link] << " " << [Link];

Stack (LIFO - Last In First Out)

 Only top element is accessible.

Stack Operations

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

int main() {
stack<int> s;
[Link](10);
[Link](20);
cout << [Link](); // 20
[Link]();
return 0;
}

4 BBN
 Queue (FIFO - First In First Out)

 Elements are inserted at back and removed from front.

Queue Example

#include <queue>
using namespace std;

queue<int> q;
[Link](10);
[Link](20);
cout << [Link](); // 10
[Link]();

Priority Queue

 Elements are ordered by priority (max-heap by default).

Priority Queue Example

priority_queue<int> pq;
[Link](10);
[Link](30);
[Link](20);
cout << [Link](); // 30 (highest priority)

For min-heap, use:

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

Maps and Sets

Maps
 Implemented as self-balancing trees (like Red-Black Trees), leading to O(log n) time
complexity for:
o Insertion, Deletion, and Search.
 Unordered maps use hash tables, providing O(1) average time complexity but O(n)
in the worst case.
Sets
 Store only unique values in sorted order.
 lower_bound() returns the smallest value that is not less than a given input.
Example:
#include <iostream>
#include <map>
#include <set>

int main() {
std::map<int, std::string> mp;
mp[1] = "One";

5 BBN
 mp[2] = "Two";
mp[3] = "Three";
std::cout << "Value at key 2: " << mp[2] << std::endl;

std::set<int> s = {5, 1, 3, 4, 2};

std::cout << "First element in set: " << *[Link]() << std::endl;
}

Lower Bound and Upper Bound

 lower_bound(): First position where a value can be inserted while maintaining order.
 upper_bound(): Position where a strictly greater value exists.
 Requires sorted data for accuracy.
Example:
#include <iostream>
#include <set>

int main() {
std::set<int> s = {10, 20, 30, 40, 50};
auto lb = s.lower_bound(30);//30
auto ub = s.upper_bound(30);//40
std::cout << "Lower bound of 30: " << *lb << std::endl;
std::cout << "Upper bound of 30: " << *ub << std::endl;
}

Sorting Arrays and Vectors

 Use sort() function to sort arrays and vectors.
 Custom comparator functions allow sorting in descending order.
 Sorting pairs based on second values.
Example: Sorting a Vector
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
std::vector<int> v = {4, 1, 3, 5, 2};
std::sort([Link](), [Link]());
for (int x : v) std::cout << x << " ";
}

Custom Comparators and Reverse Operations

 Custom comparators for sorting pairs.
 Reversing a vector using reverse() function.
 Generating lexicographical permutations of a string.
Example:
#include <iostream>
#include <vector>

6 BBN
#include <algorithm>

bool cmp(std::pair<int, int> a, std::pair<int, int> b) {

if ([Link] == [Link])
return [Link] < [Link];
return [Link] < [Link];
}

int main() {
std::vector<std::pair<int, int>> vp = {{1, 3}, {2, 2}, {3, 1}};
std::sort([Link](), [Link](), cmp);
for (auto p : vp)
std::cout << "(" << [Link] << ", " << [Link] << ") ";
}
Permutations and Basic STL Functions
 next_permutation() & prev_permutation() for generating sequences.
 Basic functions: swap(), min(), max().
 Binary search for checking value existence.
 Counting set bits in an integer using built-in GCC functions.
Example: Finding Next Permutation
#include <iostream>
#include <algorithm>

int main() {
std::string s = "abc";
std::next_permutation([Link](), [Link]());
std::cout << "Next permutation: " << s << std::endl;
}
Built-in Functions
 popcount() for counting set bits in integers.
 Overview of STL containers: maps, sets, queues, lists, deques.
 Iterators, custom comparators, and time complexities.
 Encouragement for hands-on practice!
Example: Using __builtin_popcount()
#include <iostream>
int main() {
int x = 15; // Binary: 1111
std::cout << "Set bit count: " << __builtin_popcount(x) << std::endl;
}

Strings
What is a String?
 In programming, a string is a sequence of characters enclosed in double quotes (" ").
 Example: "College" is a string.
 A string can be a word, phrase, or even a complete sentence.

7 BBN
Character Arrays vs Strings
 Before understanding strings, it's important to learn about character arrays.
 In C++, a character array is a sequence of characters stored in contiguous memory
locations.
 Example of a character array:
 char str[] = {'A', 'B', 'C'};
Special Feature of Character Arrays
 Character arrays can also store strings.
 However, to be considered a valid string, a special character must be added at the end:
null character (\0).
 Example:
 char str[] = {'A', 'B', 'C', '\0'};
 The null character (\0) marks the end of the string.
 Without \0, the character array does not behave like a proper string.
Memory Allocation in Character Arrays
 Each character in a character array takes 1 byte of memory.
Printing Character Arrays
 If we print a normal integer array, it gives a memory address.
 But if we print a character array, it prints the entire string stored in it.
Example:
char str[] = "ABC";
cout << str; // Output: ABC
 This happens because C++ treats character arrays with a null character (\0) as strings.
Calculating String Length
 To find the length of a string, we use the function strlen().
Example:
cout << strlen(str);
Assigning Strings to Character Arrays
 Instead of storing individual characters, we can directly assign a string literal.
Example:
char str[] = "Hello";
 String literals are constant values that do not change.
Accessing Individual Characters
 Just like arrays, we can access individual characters of a string using indexing.
Example:
char str[] = "Hello";
cout << str[1]; // Output: e
 If we try to access the index of the null character (\0), nothing is displayed.
Using String Class:
string str = "Apna College";
Advantages of Strings Over Character Arrays
 No need to specify size.
 Supports dynamic resizing.
 Easier to perform operations like concatenation and comparison.
Operations on Strings
 Concatenation (Joining Strings):

8 BBN
string s1 = "Bit By ";
string s2 = "Note";
string s3 = s1 + s2; // Result: "Bit By Note"
 Comparison:
if (s1 == s2) {
cout << "Strings are equal";
} else {
cout << "Strings are not equal";
}
Taking String Input
 To take input for a string, we use getline().
Syntax:
getline(cin, string_name);
 This method allows us to take a full sentence as input, including spaces.
Looping Through a String
 We can use loops to iterate through a string.
 Using a for-loop with an index:
for (int i = 0; i < [Link](); i++) {
cout << str[i] << " ";
}
 Using a for-each loop:
for (char c : str) {
cout << c << " ";
}

Commonly Used String Functions in C++

Functions and
Category Operators Functionality

String Length length() or size() It will return the length of the string.

To access individual characters using

array[index]
array indexing.

Accessing Used to access a character at a specified

at()
Characters index.

+ operator is used to concatenate two

+
strings.
Appending and
Concatenating
Strings append() [Link](str2);

9 BBN
 Functions and
Category Operators Functionality

You can compare strings using the ==

==
operator.

String Comparison compare() [Link](str2).

// Copy two characters of s1

(starting from index 3)
substr()
string r = [Link](3, 2);
Substrings

Searching find() [Link](sub);

replace() [Link](first, last, str2)

insert() [Link]([Link]() + 8, 'G');

Modifying Strings erase() [Link](first, last).

Permutation in String
Problem Statement:
We need to check if a permutation of string s1 exists as a substring in string s2.

Approach:
1. Store Frequency of s1: Create a frequency array for s1.
2. Sliding Window on s2: Traverse s2 using a window of size [Link], updating the
frequency dynamically.
3. Compare Frequency Arrays: If the window frequency matches s1's frequency, return
true.
4. Edge Case: If no matching window is found, return false.

Step 1: Store Frequency of s1

10 BBN
We create an integer array of size 26 (for lowercase English letters) and store the frequency of
characters in s1.
int[] frequency = {0};
for (int i = 0; i < [Link](); i++) {
frequency[[Link](i) - 'a']++;
}

Step 2: Initialize Sliding Window on s2

We create a window of size [Link]() in s2 and maintain a frequency array for it.
int[] windowFreq = {0};
for (int i = 0; i < [Link](); i++) {
windowFreq[[Link](i) - 'a']++;
}
Now, our window contains the frequency of the first [Link]() characters in s2.

Step 3: Compare Frequencies and Slide the Window

If windowFreq matches frequency, return true. Otherwise, slide the window one step right by
adding a new character and removing the old one.
for (int i = [Link](); i < [Link](); i++) {
if ([Link](frequency, windowFreq)) {
return true;
}
// Add new character
windowFreq[[Link](i) - 'a']++;
// Remove old character
windowFreq[[Link](i - [Link]()) - 'a']--;
}
// Final check for the last window
return [Link](frequency, windowFreq);

Step 4: Edge Case Handling

 If [Link]() > [Link](), return false immediately.
 If s1 or s2 is empty, handle it separately.
if ([Link]() > [Link]()) return false;
if ([Link]() || [Link]()) return false;

Final Optimized Code

#include <iostream>
#include <vector>
using namespace std;
// Function to check if two frequency arrays are equal
bool areEqual(vector<int> &freq1, vector<int> &freq2) {
for (int i = 0; i < 26; i++) {
if (freq1[i] != freq2[i])
return false;
}
return true;
}

11 BBN
// Function to check if any permutation of pattern is in text
bool checkPermutationInText(string text, string pattern) {
int n = [Link](), m = [Link]();
if (m > n) return false;
vector<int> textFreq(26, 0), patternFreq(26, 0);
// Fill frequency array for the first 'm' characters
for (int i = 0; i < m; i++) {
textFreq[text[i] - 'a']++;
patternFreq[pattern[i] - 'a']++;
}
// Check for the first window
if (areEqual(textFreq, patternFreq)) return true;

// Slide over the text

for (int i = m; i < n; i++) {
textFreq[text[i] - 'a']++; // Add new character
textFreq[text[i - m] - 'a']--; // Remove old character
if (areEqual(textFreq, patternFreq)) return true;
}
return false;
}

Time Complexity Analysis:

 O(26) ≈ O(1) for frequency comparison (since fixed-size alphabet).
 O([Link]() + [Link]()) for frequency calculation and sliding window.
 Overall: O([Link]()), which is optimal.
Space Complexity:
 O(1) since the frequency arrays have a fixed size of 26.

# String Compression in C++

Introduction
String compression is a technique used to reduce the size of a given character sequence by
replacing consecutive duplicate characters with a single character followed by its frequency.
Problem Statement
We are given an array of characters, and we need to compress it in-place by following these
rules:
1. If a character appears multiple times consecutively, replace it with the character followed
by its count.
2. If a character appears only once, it remains unchanged.
3. The compressed characters should be stored in the original array.
4. Return the new length of the array after compression.
Example
Input:
['a', 'a', 'b', 'b', 'c', 'c', 'c']
Output:
['a', '2', 'b', '2', 'c', '3'] // New length: 6
Approach

12 BBN
 1. Initialize Pointers: Use a pointer i to traverse the array and a pointer index to track the
position in the compressed array.
2. Count Consecutive Characters: Use a loop to count consecutive occurrences of each
character.
3. Modify the Array In-Place:
o Store the character at the current index.
o If the character count > 1, convert the count to a string and store each digit in the
array.
4. Return the New Length: The final value of index gives the new length of the
compressed array.
Implementation in C++
#include <iostream>
#include <vector>
using namespace std;

int compress(vector<char>& chars) {

int index = 0; // Position in the modified array
int i = 0; // Traversal pointer
int n = [Link]();

while (i < n) {
char currentChar = chars[i];
int count = 0;
// Count occurrences of currentChar
while (i < n && chars[i] == currentChar) {
count++;
i++;
}

// Store the character

chars[index++] = currentChar;

// Store the count if greater than 1

if (count > 1) {
string countStr = to_string(count);
for (char c : countStr) {
chars[index++] = c;
}
}
}

return index; // New length of compressed array

}

int main() {
vector<char> chars = {'a', 'a', 'b', 'b', 'c', 'c', 'c'};
int newLength = compress(chars);

13 BBN
 // Output compressed characters
for (int i = 0; i < newLength; i++) {
cout << chars[i] << " ";
}
cout << "\nNew Length: " << newLength << endl;
return 0;
}
Explanation of Code
1. We initialize index = 0 to keep track of the compressed array position.
2. The outer while loop iterates through the input array.
3. The inner while loop counts occurrences of a character.
4. The character is stored in chars[index].
5. If the count is greater than 1, we convert it to a string and store each digit separately.
6. Finally, we return index as the new length of the array.

Counting Prime Numbers from 1 to n

Problem Statement
We need to find the count of prime numbers in a given range from 1 to n. This problem is also
available on LeetCode as Problem 204: Count Primes.
Understanding the Approach
1. We are given an integer n, and we need to count how many prime numbers exist strictly
less than n.
2. Prime Number Definition: A prime number is a number greater than 1 that has exactly
two divisors: 1 and itself.
3. Example: If n = 50, the prime numbers less than 50 are:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47
So, the total count is 15.
Approach: Sieve of Eratosthenes
1. Assumption: We assume all numbers from 2 to n-1 are prime initially.
2. Marking Non-Primes:
o Start from 2 (first prime number) and mark all its multiples as non-prime.
o Move to the next unmarked number and repeat the process.
3. Final Count: After marking, the remaining numbers that are still marked as prime are
counted.
Steps to Implement
1. Create an array isPrime of size n and initialize all values to true.
2. Set isPrime[0] and isPrime[1] to false since 0 and 1 are not prime.
3. Iterate from 2 to sqrt(n):
o If isPrime[i] is true, mark all multiples of i as false.
4. Count the remaining true values in isPrime.
Code Implementation in C++
#include <iostream>
#include <vector>
using namespace std;

14 BBN
int countPrimes(int n) {
if (n <= 1) return 0;
vector<bool> isPrime(n, true);
isPrime[0] = isPrime[1] = false;

for (int i = 2; i * i < n; i++) {

if (isPrime[i]) {
for (int j = i * i; j < n; j += i) {
isPrime[j] = false;
}
}
}

int count = 0;
for (int i = 2; i < n; i++) {
if (isPrime[i]) count++;
}
return count;
}

int main() {
int n;
cout << "Enter n: ";
cin >> n;
cout << "Number of primes less than " << n << " is: " << countPrimes(n) << endl;
return 0;
}
Time Complexity
 O(ns log n) due to the Sieve of Eratosthenes, which is efficient for large values of n.
Space Complexity
 O(n) for storing the boolean vector isPrime.

What is GCD?
The Greatest Common Divisor (GCD) of two numbers is the largest number that divides both
of them without leaving a remainder.
For example:
 GCD(12, 18) = 6 because 6 is the largest number that divides both 12 and 18.
 GCD(35, 10) = 5 because 5 is the largest number that divides both 35 and 10.

Method 1: Brute Force Approach

💡 Idea: Check every number from 1 to min(a, b) and find the largest one that divides both.
Steps:
1. Take two numbers a and b.
2. Find the minimum of a and b, say minVal.
3. Start a loop from 1 to minVal:

15 BBN
 o If i divides both a and b, update gcd.
4. Print the final value of gcd.
🔹 Example:
 Input: a = 12, b = 18
 Common divisors: 1, 2, 3, 6
 Largest one = 6 → This is the GCD.

Method 2: Euclidean Algorithm (Efficient)

💡 Idea: Instead of looping, we use the mathematical property:

where a % b gives the remainder when a is divided by b.

Repeat this until b becomes 0. The remaining a will be the GCD.
Steps:
1. If b = 0, return a (base case).
2. Otherwise, replace a with b and b with a % b.
3. Repeat step 2 until b = 0.
4. Return a as the GCD.
🔹 Example:
 Input: a = 12, b = 18
 Step 1: GCD(12, 18) → GCD(18, 12)
 Step 2: GCD(18, 12) → GCD(12, 6)
 Step 3: GCD(12, 6) → GCD(6, 0)
 Since b = 0, answer = 6.

C++ Program
Here’s the C++ code implementing both methods:
#include <iostream>
using namespace std;

// Method 1: Brute Force

int gcdBruteForce(int a, int b) {
int gcd = 1; // Store GCD
for (int i = 1; i <= min(a, b); i++) {
if (a % i == 0 && b % i == 0) {
gcd = i; // Update GCD
}
}
return gcd;
}
// Method 2: Euclidean Algorithm
int gcdEuclidean(int a, int b) {
while (b != 0) { // Loop until remainder is 0
int temp = b;
b = a % b;
a = temp;

16 BBN
 }
return a; // GCD found
}

int main() {
int a, b;
cout << "Enter two numbers: ";
cin >> a >> b;

cout << "GCD (Brute Force) of " << a << " and " << b << " is: " << gcdBruteForce(a, b) <<
endl;
cout << "GCD (Euclidean) of " << a << " and " << b << " is: " << gcdEuclidean(a, b) <<
endl;

return 0;
}
Reversing an Integer & Checking for Palindrome in
C++
1. Reversing an Integer
To reverse a given integer, we extract digits one by one and adjust the reversed number by
multiplying it by 10 and adding the extracted digit.
Steps to Reverse a Number:
1. Initialize reverseNumber as 0.
2. Extract the last digit of n using n % 10.
3. Update reverseNumber as reverseNumber * 10 + digit.
4. Remove the last digit from n using n / 10.
5. Repeat until n becomes 0.
6. Handle the case where reversing the number causes overflow.
C++ Code for Reversing an Integer:
#include <iostream>
#include <climits>
using namespace std;

int reverseInteger(int n) {
int reverseNumber = 0;

while (n != 0) {
int digit = n % 10;

// Check for overflow before updating reverseNumber

if (reverseNumber > INT_MAX / 10 || reverseNumber < INT_MIN / 10) {
return 0; // Return 0 if the number goes out of range
}

reverseNumber = reverseNumber * 10 + digit;

17 BBN
 n /= 10;
}

return reverseNumber;
}

int main() {
int num;
cout << "Enter a number: ";
cin >> num;

int reversed = reverseInteger(num);

cout << "Reversed Number: " << reversed << endl;

return 0;
}

2D Arrays in C++
What is a 2D Array?
A 2D array is like a table with rows and columns, used to store data in a structured format. It
is also called a matrix in programming.
For example, if we have a 4×3 matrix, it means:
 4 rows (horizontal lines)
 3 columns (vertical lines)
Declaring a 2D Array in C++
We use square brackets [ ] to define the number of rows and columns.
int matrix[4][3]; // 4 rows and 3 columns
Initializing a 2D Array
We can initialize a 2D array with values like this:
int matrix[4][3] = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9},
{10, 11, 12}
};
Each { } represents a row.
Accessing Elements in a 2D Array
To access an element, we need row and column indexes (starting from 0).
cout << matrix[2][1]; // Prints 8 (Row index 2, Column index 1)
We can also modify an element:
matrix[2][1] = 18; // Changes value from 8 to 18
Printing a 2D Array using Loops
We use nested loops to print all elements row-wise.
for(int i = 0; i < 4; i++) { // Loop for rows
for(int j = 0; j < 3; j++) { // Loop for columns

18 BBN
 cout << matrix[i][j] << " ";
}
cout << endl; // Move to the next row
}
Output:
1 2 3
4 5 6
7 8 9
10 11 12
Passing a 2D Array to a Function
When passing a 2D array to a function, we also pass the number of columns:
void printMatrix(int matrix[][3], int rows) {
for(int i = 0; i < rows; i++) {
for(int j = 0; j < 3; j++) {
cout << matrix[i][j] << " ";
}
cout << endl;
}
}
Call this function with:
printMatrix(matrix, 4);

Finding the Diagonal Sum in a Square Matrix

1. We need to find the sum of both primary and secondary diagonals in a square
matrix.
2. Primary diagonal → Elements at (0,0), (1,1), (2,2)... (row = col).
3. Secondary diagonal → Elements at (0,n-1), (1,n-2), (2,n-3)... (row + 1 = col-1).
4. If n is odd, the middle element is counted twice, so subtract it once.
C++ Code
#include <iostream>
using namespace std;

void DigSum(int arr[][4], int size) // Fixed parameter declaration

{
int leftDsum = 0, rightDsum = 0;
// Left diagonal sum
for (int i = 0; i < size; i++)
{
leftDsum += arr[i][i];
}
// Right diagonal sum
for (int i = 0, j = size - 1; i < size; i++, j--)
{
rightDsum += arr[i][j];
}
cout << "Left Sum: " << leftDsum << endl;

19 BBN
 cout << "Right Sum: " << rightDsum << endl;
}

int main()
{
int nums[4][4] = { {1, 2, 3, -4},
{-5, -6, -7, 8},
{-9, 0, -11, 0},
{-9, 10, -11, 0} };

DigSum(nums, 4); // Function call with correct arguments

return 0;
}

2D Vectors
 Instead of fixed-size 2D arrays, we can use 2D vectors for dynamic resizing.
 Advantage: Each row can have a different number of columns.
Defining a 2D Vector
#include <iostream>
#include <vector>
using namespace std;

int main() {
vector<vector<int>> matrix = {
{1, 2, 3},
{4, 5, 6, 7}, // Extra elements in this row
{8, 9, 10}
};

// Printing the 2D Vector

for (int i = 0; i < [Link](); i++) {
for (int j = 0; j < matrix[i].size(); j++) {
cout << matrix[i][j] << " ";
}
cout << endl;
}
return 0;
}
Key Differences Between 2D Arrays and 2D Vectors
Feature 2D Array 2D Vector

Size Fixed Dynamic

Memory Static Dynamic Allocation

20 BBN
Feature 2D Array 2D Vector

Resizing Not possible Possible at runtime

Row Size Fixed for all rows Can vary per row

Searching for a Target in a 2D Matrix

Recognizing the Pattern for

Optimization
1. Binary Search Heuristic:
o Whenever we see logarithmic time
complexity, we should think about
Binary Search.
o Binary Search is efficient when
dealing with sorted data.
2. Understanding the Sorted Matrix:
o The given matrix has two sorting
properties:
 Row-wise sorting → Values increase from left to right in each row.
 Column-wise ordering → The first element of each row is greater than the
last element of the previous row.
o This structure means that the matrix can be treated as a sorted 1D array
conceptually.
Applying Binary Search on 2D Matrix
 Since the matrix follows a sorted order, we can visualize it as a flattened sorted
array and apply binary search.
 We use an index mapping approach:
o Consider the 2D matrix as a 1D sorted array of size n * m.

21 BBN
 o Use mid = (low + high) / 2 to find the middle element.
o Compare matrix[row][col] with the target:
 If equal, return true.
 If less, move to the right half (low = mid + 1).
 If greater, move to the left half (high = mid - 1).
Code:-
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int row=-1;
int start=0, end=[Link]()-1;
int cols=matrix[0].size()-1;
while(start<=end){
int mid=start+(end-start)/2;
if(target>=matrix[mid][0] && target<=matrix[mid][cols]){
row=mid;
break;
}
else if(target<matrix[mid][0]){
end=mid-1;
}
else{
start=mid+1;
}
}
if(row==-1)return false;
start=0, end=cols;
while(start<=end){
int mid=start+(end-start)/2;
if(target==matrix[row][mid])return true;

else if(target<matrix[row][mid]){
end=mid-1;
}
else{
start=mid+1;
}
}
return false;

}
};

Searching in a Sorted 2D Matrix

22 BBN
Why Can't We Use the Previous Approach?
In the previous problem, each row’s first element was greater than the last element of the
previous row. However, in this problem, row values overlap in range.

For example, if we search for 5, it could exist in multiple overlapping ranges instead of a single
unique row. This means we cannot apply the previous approach directly.
How to Solve This Problem?
Since the data is sorted, a binary search or its variation should be considered.
Observations:
 The smallest value in the matrix will always be at (0,0) (top-left corner).
 The largest value will always be at (M-1, N-1) (bottom-right corner).
Choosing a Search Strategy
To apply binary search, we need a search range within which our target value exists.
We define our search space as:
 Start from (0, N-1) → Top-right corner
 Midpoint selection strategy:
o If the midpoint value = target, we return true.
o If the midpoint value > target, we move left.
o If the midpoint value < target, we move down.
By always reducing search space row-wise or column-wise, we ensure an efficient search.
Why Start from the Top-Right Corner?
 If we choose any random middle element, it may lead to multiple search directions.

23 BBN
  Corner elements reduce possibilities, helping us eliminate larger portions of the
matrix.
 At (0, N-1):
o If target < matrix[0][N-1], move left (reduce column).
o If target > matrix[0][N-1], move down (increase row).
Thus, starting from top-right reduces unnecessary comparisons and makes the search more
efficient.
class Solution {
public:
bool searchMatrix(vector<vector<int>>& mat, int target) {
int row=0,col=mat[0].size()-1;
while(row<[Link]() && col<mat[0].size()){
if(mat[row][col]==target)return true;
else if(mat[row][col]>target)col--;
else row++;
}
return false;
}
};
Spiral Matrix Traversal - C++ Notes
Introduction
 The Spiral Matrix is a common 2D array problem frequently asked in interviews.
 It involves traversing a given matrix in a spiral order and storing the elements in a
specific sequence.
 Example problem: Leetcode #54 - Spiral Matrix.
Understanding the Problem
 Given an m × n matrix, traverse it in a spiral pattern:
o Start from the top-left corner.
o Move left to right along the top boundary.
o Move top to bottom along the right boundary.
o Move right to left along the bottom boundary.
o Move bottom to top along the left boundary.
o Repeat for the inner layers until all elements are covered.
Example
Consider the given 4×4 matrix:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
Spiral order traversal:
1 → 2 → 3 → 4 ↓ 8 → 12 → 16 ← 15 ← 14 ← 13 ↑ 9 → 5 → 6 → 7 ↓ 11 → 10
Output: [1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10]
Approach
 Use four boundary markers:
o startRow (initially 0)
o endRow (m - 1)
o startCol (0)

24 BBN
 oendCol (n - 1)
 Use a loop to iterate through boundaries:
1. Top boundary → left to right (fixed row)
2. Right boundary → top to bottom (fixed column)
3. Bottom boundary → right to left (fixed row)
4. Left boundary → bottom to top (fixed column)
5. Shrink boundaries after each traversal.
Code Implementation (C++)
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> ans;
int srow=0,scol=0;
int erow=[Link]()-1,ecol=matrix[0].size()-1;
while(srow<=erow && scol<=ecol){
//top
for(int col=scol;col<=ecol;col++){
ans.push_back(matrix[srow][col]);
}
//right
for(int row=srow+1;row<=erow;row++){
ans.push_back(matrix[row][ecol]);
}
if(srow !=erow){
//bottom
for(int col=ecol-1;col>=scol;col--){
ans.push_back(matrix[erow][col]);
}
}
if(scol !=ecol){
//left
for(int row=erow-1;row>=srow+1;row--){
ans.push_back(matrix[row][scol]);
}
}

srow++;
erow--;
scol++;
ecol--;
}
return ans;
}
};
Time Complexity
 O(m × n) → Each element is visited once.
Space Complexity
 O(1) → Uses only extra space for output array.

25 BBN
Finding a Pair with Target Sum using Unordered
Map
Problem Statement

Given an array of integers nums and an integer target, return indices of the two numbers such that
they add up to target.

You may assume that each input would have exactly one solution, and you may not use
the same element twice.

You can return the answer in any order.

Approach
1. Pick the First Value: We iterate over the array and pick an element as the first value.
2. Calculate the Second Value: The second value can be found using:
Second Value = Target − First Value
3. Check if Second Value Exists:
o If it exists in the remaining array, we return both indices.
o If not, we store the first value in an unordered map.
Why Use Unordered Map?
 Unordered maps allow fast searching (average O(1) time complexity).
 It helps us quickly check if the second value exists in the stored elements.

C++ Code Implementation

class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> m;
vector<int> ans;
for(int i=0;i<[Link]();i++){
int first=nums[i];
int sec=target-first;
if([Link](sec) != [Link]()){
ans.push_back(i);
ans.push_back(m[sec]);
break;
}
m[first]=i;
}
return ans;
}

26 BBN
};

Time Complexity Analysis

Outer Loop runs O(n). Unordered Map Operations (find and insert) take O(1) on average.
Overall Time Complexity: O(n).

Hashing and Repeating Values (Leetcode Problem

2965)
Problem Statement:

Approach to Solve the Problem:

1. Finding the Repeating Number (a)
 We use a set to track numbers we have seen.
 We traverse the grid, inserting each number into the set.
 If we find a number already in the set, that is our repeating number a.
2. Finding the Missing Number (b)
 The sum of numbers from 1 to n² can be calculated using the formula:
 Compute the actual sum from the grid.
 Using the equation:
 We can find b, the missing value.

Code Implementation in C++:

class Solution {
public:
vector<int> findMissingAndRepeatedValues(vector<vector<int>>& grid) {
unordered_set<int> s;
vector<int> ans;
int n=[Link]();
int a,b;
int actualSum=0,expectedSum=0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
actualSum+=grid[i][j];
if([Link](grid[i][j])!=[Link]()){
a=grid[i][j];
ans.push_back(a);
}
[Link](grid[i][j]);
}
}
expectedSum=(n*n)*(n*n+1)/2;
b=expectedSum+a -actualSum;

27 BBN
ans.push_back(b);
return ans;
}
};

Explanation with Example:

Given Grid:
1 2 3
4 9 6
7 9 8
 Numbers should be from 1 to 9.
 Repeating number a = 9 (appears twice).
 Missing number b = 5 (does not appear in the grid).
 Formula Calculation:
o Expected sum =
o Actual sum = 47 (since 9 appears twice and 5 is missing)
o Using formula:

Time Complexity: O(n²).

Space Complexity: O(n²) in the worst case, due to storing values in a set.

Find the Duplicate Number

Given an array of integers nums containing n + 1 integers where each integer is in the range [1,
n] inclusive. There is only one repeated number in nums, return this repeated number.
You must solve the problem without modifying the array nums and using only constant extra space.

Approach:-
Concept of Linked List
 A linked list is a collection of nodes where each node points to the next one.
Example: 1 -> 2 -> 3 -> 4 -> 5
 If a node points back to a previous node, a cycle is formed.
Reimagining Array as a Linked List
 Each index of an array is treated as a node in the linked list.
 Each element at that index points to the next node.
 Example:
Array: [3, 1, 3, 4, 2]

28 BBN
Index: 0 1 2 3 4
o Index 0 → Index 3 (since arr[0] = 3)
o Index 3 → Index 4 (since arr[3] = 4)
o Index 4 → Index 2 (since arr[4] = 2)
o Index 2 → Index 3 (since arr[2] = 3) → Cycle detected
Slow-Fast Pointer Approach
1. Step 1: Detect Cycle
o Use two pointers: Slow (moves 1 step) & Fast (moves 2 steps).
o If Slow meets Fast, a cycle exists.
2. Step 2: Find Cycle Start
o Move Slow to the start, keep Fast at meeting point.
o Move both one step at a time until they meet again.
Meeting point = Start of the cycle = Duplicate number.
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int slow=nums[0],fast=nums[0];
do{
slow=nums[slow];
fast=nums[nums[fast]];
}while(slow!=fast);
slow=nums[0];
while(slow!=fast){
slow=nums[slow];
fast=nums[fast];
}
return slow;
}
};

Four Sum Problem

Problem Statement

Approach - Two Pointer Technique

29 BBN
Since this is a variation of Two Sum and Three Sum, we use a Two Pointer approach.
Steps to Solve
1. Sort the array (Two-pointer works
efficiently in sorted arrays).
2. Pick the first number nums[i] using a
loop.
3. Pick the second number nums[j]
using another loop (j = i + 1).
4. Use two pointers (k, l) to find the
remaining two numbers:
o k = j + 1 (start pointer)
o l = n - 1 (end pointer)
5. Check the sum of nums[i] + nums[j]
+ nums[k] + nums[l]:
o If equal to target, store the combination.
o If less than target, move k++ to increase sum.
o If greater than target, move l-- to decrease sum.
6. Avoid duplicates by skipping repeated values.

Code Implementation (C++)

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> fourSum(vector<int>& nums, int target) {

sort([Link](), [Link]());
vector<vector<int>> result;
int n = [Link]();

for (int i = 0; i < n - 3; i++) {

if (i > 0 && nums[i] == nums[i - 1]) continue; // Avoid duplicates
for (int j = i + 1; j < n - 2; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) continue; // Avoid duplicates

int k = j + 1, l = n - 1;
while (k < l) {
long sum = (long)nums[i] + nums[j] + nums[k] + nums[l];
if (sum == target) {
result.push_back({nums[i], nums[j], nums[k], nums[l]});
while (k < l && nums[k] == nums[k + 1]) k++; // Skip duplicates
while (k < l && nums[l] == nums[l - 1]) l--; // Skip duplicates
k++; l--;
}
else if (sum < target) k++;
else l--;
}
}
}
return result;
}

30 BBN
Time Complexity Analysis
 Sorting the array: O(N log N)
 Two nested loops (i and j): O(N²)
 Two-pointer search (k and l): O(N)
 Overall Complexity: O(N³)
Space Complexity
 O(1) (Ignoring output storage)

Subarray Sum Equals K

Problem Statement: Find the number of subarrays whose sum equals k.

Step-by-Step Approach
Step 1: Use a HashMap to Store Prefix Sum
Frequencies
unordered_map<int, int> m;
 We use an unordered map (m) to store
how many times a particular sum has
appeared before.
 Key: sum (prefix sum up to a certain index)
 Value: Count of how many times this
sum appeared

31 BBN
Step 2: Initialize Variables
int sum = 0, count = 0;
m[0] = 1;
 sum = 0: Keeps track of the running sum (prefix sum).
 count = 0: Stores the number of valid subarrays found.
 m[0] = 1: Important! It ensures we correctly count subarrays starting from index 0.

Step 3: Traverse Through Array

for (int i = 0; i < [Link](); i++) {
 We go through each element in nums.

Step 4: Update the Running Sum

sum += nums[i];
 Keep adding each element to sum (prefix sum).

Step 5: Check if There Exists a Subarray with Sum k

if ([Link](sum - k) != [Link]()) {
count += m[sum - k];
}
sum - k tells us if a previous prefix sum exists such that the difference between them equals k.
 If found, add its frequency to count (since there are that many valid subarrays).

Step 6: Store the Prefix Sum in HashMap

m[sum]++;
 Store the sum in the map to keep track of its frequency for future checks.

Final Step: Return the Total Count

return count;

Final Optimized Code

class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int,int> m;
int sum=0,count=0;
m[0]=1;
for(int i=0;i<[Link]();i++){
sum+=nums[i];
if([Link](sum-k)!=[Link]()){
count+=m[sum-k];
}
m[sum]++;
}
return count;
}
};

32 BBN
Understanding With an Example
Input:
nums = {1, 2, 3}, k=3
Dry Run:
Inde nums[i su sum - k m[sum - k] Exists? coun HashMap (m)
x ] m t
0 1 1 -2 ❌ No 0 {0:1, 1:1}

1 2 3 0 ✅ Yes (m[0]=1) 1 {0:1, 1:1, 3:1}

2 3 6 3 ✅ Yes (m[3]=1) 2 {0:1, 1:1, 3:1, 6:1}

Output: 2 ✅
(Subarrays: [1,2] and [3])

Time Complexity Analysis

 O(N): We traverse nums once and perform O(1) operations per element.

Recursion
1. What is Recursion?
o Recursion happens when a function calls itself.
o This is different from regular function calls where one function calls another.
o It continues calling itself until it reaches a stopping condition (Base Case).
2. How Does Recursion Work?
o Each function call does a small part of the work.
o The remaining work is passed on to the next function call.
o Eventually, it reaches the simplest problem (Base Case), where it stops.

Steps to Solve a Recursion Problem

Example: Print numbers from n to 1 using recursion
📌 Problem Statement: Given an integer n, print all numbers from n to 1 using recursion.

Step-by-Step Approach
Step 1: Identify the Base Case
 The recursion must stop at some point.
 Base Case: If n == 1, print 1 and stop further calls.
Step 2: Identify the Recursive Case
 If n > 1,
o Print n.
o Call the function again with n-1.
o This will print the next smaller number.
Step 3: Write the Recursive Function
#include <iostream>
using namespace std;
void printNumbers(int n) {
// Base case: stop when n reaches 1

33 BBN
 if (n == 1) {
cout << 1 << endl;
return;
}
// Print the current number
cout << n << endl;
// Recursive call with n-1
printNumbers(n - 1);
}

Understanding the Execution

📌 Example Input: n = 4
📌 Function calls breakdown:
printNumbers(4)→prints 4→calls printNumbers(3)

prints 3→calls printNumbers(2)

prints 2→calls printNumbers(1)

prints 1→stops (Base Case)

📌 Output:
4
3
2
1
Understanding the Call Stack with Recursion
In C++, when a function is called, its execution details (like local variables and return addresses)
are stored in the Call Stack. Once the function completes, its stack frame is removed, and
execution returns to the previous function call.
How the Call Stack Works Internally?
Step-by-Step Execution:

Time complexity:- O(n) because function calls itself n times.

Space Complexity:- O(n) due to the recursive call stack.
Fibonacci Sequence (Using Recursion)
Introduction
 The sequence starts with 0 and 1.
 Each next term is the sum of the previous two terms.
Fibonacci Series Example
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
 Formula: Fib(n) = Fib(n-1) + Fib(n-2)
 Example:

34 BBN
 o Fib(2) = 1 + 0 = 1
o Fib(3) = 1 + 1 = 2
o Fib(4) = 2 + 1 = 3
o Fib(5) = 3 + 2 = 5
Problem Statement
Find the Nth Fibonacci number using recursion.

Example: If n = 6, output should be 8.

Recursion Concept
 Recursion: Solving a big problem by breaking it into smaller sub-problems.
 Recursive relation: Fib(n) = Fib(n-1) + Fib(n-2)
 Recursive calls continue until we reach the base case.
Base Cases
 Fib(0) = 0
 Fib(1) = 1
Recursive Function in C++
#include <iostream>
using namespace std;

// Function to calculate Fibonacci number

int fibonacci(int n) {
if (n == 0 || n == 1) return n; // Base case
return fibonacci(n - 1) + fibonacci(n - 2); // Recursive case
}

Time Complexity
 Recursive function creates a tree of function calls.
 Each call branches into two more calls.
 Time Complexity: O(2^n) (Exponential, very slow for
large n).
Space Complexity
 O(n) due to recursive function call stack.

Printing All Subsets

We will start with the problem of printing all subsets for a given array. This
problem is not limited to arrays; it can also apply to strings. Suppose we have
some characters in a string—the same logic for subsets applies to any linear data structure that
holds some elements.
For now, let's take an array as an example.
What is a Subset?
A subset is a smaller group of elements derived from a given set of elements.
For example, if we have an array with two elements:
arr = {1, 2};
The possible subsets for this array are:
1. {1} (including only 1)
2. {2} (including only 2)

35 BBN
 3. {1, 2} (including both elements)
4. {} (empty subset, containing no elements)
Thus, the total number of subsets for an array of size n is given by:
Total subsets=2n
for a given array.
Using Recursion to Generate Subsets
Recursion is a fundamental concept that helps solve many problems based on subsets.
To generate subsets, we follow this approach:
 Each element of the array has a choice:
1. Include it in the subset.
2. Exclude it from the subset.
 We apply recursion to solve this problem step by step.
 Instead of solving the entire problem at once, we break it into smaller subproblems.
 For every element in the array, we take a recursive decision to either include or
exclude it.
Example of Recursive Approach
Let's consider an array {1, 2, 3} and generate its subsets using recursion:

{1, 2, 3}, {1, 2}, {1, 3}, {1}, {2, 3}, {2}, {3}, {}
This gives us 2^3 = 8 subsets, as expected.
Recursive Code to Print Subsets (C++)
class Solution {

public:
void allsets(vector<int>& nums,vector<vector<int>>& ans,vector<int> sub,int i){
if(i==[Link]()){
ans.push_back(sub);
return;
}
sub.push_back(nums[i]);
allsets(nums,ans,sub,i+1);
sub.pop_back();
allsets(nums,ans,sub,i+1);
}

36 BBN
 vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> ans;
vector<int> sub;
allsets(nums,ans,sub,0);
return ans;
}
};
Explanation of the Code:
1. Base Condition: If we reach the end of the array, print the subset and return.
2. Recursive Steps:
o First, we exclude the current element and move to the next index.
o Then, we include the current element and again move to the next index.
o After both recursive calls, we backtrack to remove the last added element.
3. Printing: Every subset is printed at the base condition when index == [Link]().
Time Complexity Analysis
Since we generate 2^n subsets (each element has two choices), the time complexity of this
approach is O(2^n).
Handling Duplicate Elements in Subset Generation
Problem Understanding
Previously, we dealt with unique elements in the subset problem.
Now, we are considering an array that contains duplicate elements.
Key Question: How do duplicates affect subset generation?
Example
Given an array: {1, 2, 2}
 Using the previous subset approach, we generate all subsets.
 Challenge: Duplicate subsets appear in the output.
Recursive Approach for Subset Generation
1. Start with an empty subset.
2. At each index (i), choose to either include or exclude the current element.
3. Move to the next index and repeat the process.
4. Generate all subsets and handle duplicates.

37 BBN
Issue with Duplicate Subsets
 If we blindly follow inclusion/exclusion for each element, we may generate duplicate
subsets.
 The key observation:
o If we exclude a duplicate element at some point, we must continue excluding all
its occurrences in subsequent steps.
Fixing the Duplicate Issue
1. Sort the array first to group identical elements together.
2. Modify the recursive approach:
o If an element is excluded, skip all its consecutive occurrences to avoid
duplicate subsets.
Recursive Implementation Strategy
class Solution {
public:
void allsets(vector<int>& nums,vector<vector<int>>& ans, vector<int> sub,int i){

if(i==[Link]()){
ans.push_back({sub});
return;
}
sub.push_back(nums[i]);
allsets(nums,ans,sub,i+1);
sub.pop_back();
while(i+1<[Link]()&&nums[i+1]==nums[i])i++;
allsets(nums,ans,sub,i+1);

}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<vector<int>> ans;
vector<int> sub;
sort([Link](),[Link]());

38 BBN
 allsets(nums,ans,sub,0);
return ans;
}
};
Complexity Analysis
 The total number of subsets is O(2ⁿ), but removing duplicates reduces redundant
calculations.
 Sorting takes O(n log n), and the subset generation process runs in O(2ⁿ) (in worst-case
scenarios).
Permutations of an Array
Introduction
 The same logic applies whether the input is an array or a string.
 A permutation is a rearrangement of the elements of an array in all possible orders.
Understanding Permutations
 Given an array [1, 2, 3], the possible permutations are:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
 The total number of permutations of n elements is n! (n factorial).
Mathematical Logic Behind Permutations
 Imagine n positions that we need to fill using n elements.
 For the first position: We have n choices.
 For the second position: n-1 choices remain.
 For the third position: n-2 choices remain.
 … continues until only one choice is left.

Recursion Approach to Generate Permutations

1. Base Condition:
o If we have placed all n elements, store the permutation.
2. Recursive Case:

39 BBN
 o Swap elements to form new permutations.
o Move to the next position.
C++ Code for Generating Permutations
class Solution {
public:
void permutations(vector<int>& nums,int idx,vector<vector<int>>& ans){
if(idx==[Link]()-1){
ans.push_back(nums);
return;
}
for(int i=idx;i<[Link]();i++){
swap(nums[i],nums[idx]);
permutations(nums,idx+1,ans);
swap(nums[i],nums[idx]);
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> ans;
permutations(nums,0,ans);
return ans;
}
};
Explanation of Code
1. permutation(nums, index, result):
o Generates permutations using recursion and backtracking.
o Swaps elements to create different orders.
2. permute(nums):
o Calls the recursive function to generate all permutations.
3. main():
o Defines an array {1, 2, 3} and prints all permutations.

N-Queens Problem
Introduction
The N-Queens problem is a classic problem in computer science that helps understand
recursion and backtracking. The goal is to place N queens on an N×N chessboard so that no two
queens attack each other.
Understanding the Chessboard and Queen’s Movement
A queen in chess can attack other pieces in the following ways:
 Vertically (same column)
 Horizontally (same row)
 Diagonally (both left and right diagonals)
Thus, our task is to place N queens on the board such that none of them attack each other.
Approach: Recursion and Backtracking
The problem is solved using recursion and backtracking:
1. Place a queen in a row.
2. Move to the next row and try placing the next queen in a valid position.

40 BBN
 3. If a row has no valid positions, backtrack and change the previous queen’s position.
4. Repeat until all N queens are successfully placed.

Algorithm (Steps to Solve the Problem)

1. Start placing queens from row 0.
2. For each column in the current row, check if it is a safe position.
3. If safe, place the queen and move to the next row.
4. If no column is safe in the current row, backtrack to the previous row and move the queen
to the next possible column.
5. Repeat until all queens are placed or backtrack until there’s no solution.

class Solution {
public:
bool isSafe(vector<string>& board, int row, int col, int n){
//row
int i=0;
while(i<n){
if(board[row][i]=='Q')return false;
if(board[i][col]=='Q')return false;
i++;
}
//left diagnol
i=row;
int j=col;
while(i>=0&&j>=0){
if(board[i][j]=='Q')return false;
i--;
j--;
}

41 BBN
 //right diagnol
i=row,j=col;
while(i>=0&&j<n){
if(board[i][j]=='Q')return false;
i--;
j++;
}
return true;
}

void nQueens(vector<string>& board,vector<vector<string>>& ans, int n,int row){

if(row==n){
ans.push_back({board});
return;
}
for(int i=0;i<n;i++){
if(isSafe(board, row,i,n)){
board[row][i]='Q';
nQueens(board,ans,n,row+1);
board[row][i]='.';
}
}
}

vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> ans;
vector<string> board(n,string(n,'.'));
nQueens(board,ans,n,0);
return ans;
}
};

Rat Maze
Handling Validity and Base Cases in Matrix Problems using C++
Understanding the Boundary Conditions
When working with matrices, the first step is to ensure that our row and column values are within
valid boundaries. If these values are invalid, we cannot perform valid operations on the matrix.
Thus, in our base case, we define the following conditions:
if (r < 0 || c < 0 || r >= n || c >= n || matrix[r][c] == 0) {
return;
}
Here, n represents the size of the matrix. The conditions ensure that:
 r < 0 or c < 0: We are not accessing negative indices.
 r >= n or c >= n: We are within the matrix bounds.
 matrix[r][c] == 0: We do not proceed if the value in the cell is zero (invalid path).
Handling the Base Case for Finding a Solution

42 BBN
When we reach the bottom-right corner of the matrix (r == n - 1 && c == n - 1), we have found
a valid path:
if (r == n - 1 && c == n - 1) {
answer.push_back(path);
return;
}
This ensures that once we reach our goal, we store the path and return.
Handling Opposite Choices to Prevent Infinite Recursion
If we choose to move downward (r+1, c), we should not immediately move upward (r-1, c) in the
next step, as this creates an infinite loop. Similarly, moving left after moving right leads to the
same issue. To prevent this, we track visited cells.
Using a Visited Matrix to Track Paths
We maintain an n x n visited matrix, initialized with false, to track whether a cell has been
visited:
vector<vector<bool>> visited(n, vector<bool>(n, false));
Before exploring a cell, we mark it as visited:
visited[r][c] = true;
If we encounter a cell that is already visited, we return immediately:
if (visited[r][c]) return;
Once we return from recursion, we reset the cell to false to allow other paths to use it:
visited[r][c] = false;
This technique is crucial for backtracking, ensuring that previously visited cells can be
reconsidered when trying alternate paths.
Final Recursive Function with Backtracking
Here’s how the recursive function implements the above logic:
void findPath(vector<vector<int>>& matrix, vector<vector<bool>>& visited, int r, int c,
string path, vector<string>& answer) {
int n = [Link]();
if (r < 0 || c < 0 || r >= n || c >= n || matrix[r][c] == 0 || visited[r][c]) {
return;
}
if (r == n - 1 && c == n - 1) {
answer.push_back(path);
return;
}
visited[r][c] = true;
// Exploring all possible directions
findPath(matrix, visited, r + 1, c, path + "D", answer); // Down
findPath(matrix, visited, r, c + 1, path + "R", answer); // Right
findPath(matrix, visited, r - 1, c, path + "U", answer); // Up
findPath(matrix, visited, r, c - 1, path + "L", answer); // Left
// Backtracking step
visited[r][c] = false;
}

Palindrome Partitioning
Problem Statement
43 BBN
Given a string s, we need to return a vector of vectors of strings, where each vector contains
possible partitions of s that are all palindromic in nature.
Understanding the Problem
To solve this problem, we need to:
1. Generate all possible partitions of the string.
2. Filter partitions that are palindromic and store them in the answer vector.
Breaking Down the Problem
 Partitioning a String: If a string s has a length of n, we can place n - 1 cuts to generate
all possible partitions.
 Example: For string "abc":
o Partitions: {"a", "b", "c"}, {"ab", "c"}, {"a", "bc"}, {"abc"}
o We must check which of these partitions contain only palindromic substrings.
Palindrome Checking
A substring is palindromic if it reads the same forward and backward. Example:
 "aba" is a palindrome
 "abc" is not a palindrome
Recursive Approach for Solution
1. Start from the beginning of the string and try to make cuts at each index.
2. If the left substring (from start
to current index) is a palindrome,
then recursively partition the
remaining right substring.
3. Collect all palindromic partitions
and return them as a vector of
vectors.

Code Implementation
class Solution {
public:
bool isPalindrome(string p){
int start=0;
int end=[Link]()-1;
while(start<end){
if(p[start]!=p[end]){
return false;
}
start++;
end--;
}
return true;
}
void helper(string s, vector<string>& part,vector<vector<string>>& ans){
if([Link]()==0){
ans.push_back(part);

44 BBN
 return;
}
for(int i=0;i<[Link]();i++){
string p =[Link](0,i+1);
if(isPalindrome(p)){
part.push_back(p);
helper([Link](i+1),part,ans);
part.pop_back();
}
}
}
vector<vector<string>> partition(string s) {
vector<vector<string>> ans;
vector<string> part;
helper(s,part,ans);
return ans;
}
};

Merge Sort Algorithm

Introduction
Merge Sort is a divide-and-conquer algorithm that continuously splits an array into two equal
halves until each sub-array contains a single element. It then merges these sub-arrays in a
sorted manner to form a final sorted array.
Steps of Merge Sort
1. Divide the Array: Recursively split the array into two halves.

2. Sort the Sub-arrays: Continue dividing until we reach single-element arrays.

3. Merge the Sorted Arrays: Combine the sub-arrays while sorting them.
Detailed Explanation
1. Dividing the Array
o Find the middle index of the array using:

45 BBN
mid = start + (end - start) / 2;
o Recursively call merge sort on both halves:
o mergeSort(arr, start, mid);
mergeSort(arr, mid + 1, end);

2. Base Case
o The recursion stops when the array contains only one element:
if (start >= end) return;
3. Merging Process
o Merge the two sorted halves into a single sorted array.
o Use two pointers, one for each half, and compare elements.
o Place the smaller element into a temporary array and continue merging.
o Copy the merged elements back to the original array.
C++ Implementation
#include <iostream>
#include <vector>
using namespace std;
void Merge(vector<int> &nums, int start, int mid, int end)
{
int start1 = start;
int start2 = mid + 1;
vector<int> temp;
while (start <= mid && start2 <= end)
{
if (nums[start] < nums[start2])
{
temp.push_back(nums[start++]);
}
else
{
temp.push_back(nums[start2++]);
}
}
while (start <= mid)
{
temp.push_back(nums[start++]);
}
for (int i = 0; i < [Link](); i++)
{
nums[i + start1] = temp[i];
}
}
void MS(vector<int> &nums, int start, int end)
{
if (start == end)
return;
int mid = start + (end - start) / 2;
// left
MS(nums, start, mid);

46 BBN
 // right
MS(nums, mid + 1, end);
Merge(nums, start, mid, end);
}

int main()
{
vector<int> nums = {12, 9, 1, 7, -6, 5};
MS(nums, 0, [Link]() - 1);
for (int dig : nums)
{
cout << dig << " ";
}
return 0;
}
Time Complexity Analysis
 Dividing the array: O(log N) because we repeatedly split it into halves.
 Merging process: O(N) for merging two halves.
 Overall complexity: O(N log N), making it efficient for large datasets
QuickSort Algorithm
Introduction:
QuickSort is a divide and conquer sorting algorithm that sorts an array efficiently. It is based
on the pivot and partition approach.
By the end of this note, you will understand:
 The approach of QuickSort
 The time and space complexity
 The dry run of QuickSort on an array
Steps of QuickSort:
1. Choose a Pivot: Select a pivot element from the array. We will use the last element as
the pivot in our implementation.
2. Partition the Array: Rearrange the array so that:
o Elements smaller than the pivot go to the left.
o Elements greater than the pivot go to the right.
3. Recursively Apply QuickSort on the left and right subarrays.
Implementation of QuickSort in C++:
#include <iostream>
using namespace std;

// Function to partition the array

int partition(int arr[], int low, int high) {
int pivot = arr[high]; // Choosing the last element as pivot
int i = low - 1;

for (int j = low; j < high; j++) {

if (arr[j] <= pivot) {
i++;
swap(arr[i], arr[j]);

47 BBN
 }
}
swap(arr[i + 1], arr[high]);
return i + 1; // Return pivot index
}

// QuickSort function
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1); // Sort left half
quickSort(arr, pivotIndex + 1, high); // Sort right half
}
}
Dry Run Example:
Given Array: {3, 6, 1, 5, 2, 4}
1. Choose pivot = 4
2. Partitioning results in: {3, 1, 2, 4, 6, 5}
3. Recursively apply QuickSort on {3, 1, 2} and {6, 5}
4. Continue partitioning and sorting until fully sorted.
Time and Space Complexity:
 Worst Case: O(n²) → Unbalanced partitioning (already sorted/reverse sorted array
without optimization)
 Average Case: O(n log n)
 Space Complexity: O(log n) (Recursive stack space)

Inversion Count
Definition
An inversion is a pair (i, j) in an array arr such that:
 i < j (i.e., the first element appears before the second in the array)
 arr[i] > arr[j] (i.e., the first element is greater than the second)
The inversion count of an array is the total number of such pairs.

Brute Force Approach (O(N^2))

This approach uses two nested loops to compare every element with all elements that appear
after it.
Algorithm
1. Initialize count = 0
2. Use two loops:
 Outer loop runs from i = 0 to n - 1
 Inner loop runs from j = i + 1 to n
3. If arr[i] > arr[j], increase count
4. Print count after the loops

Optimized Approach Using Merge Sort (O(N log N))

We can count inversions efficiently while sorting the array using Merge Sort.

48 BBN
Key Idea
 In Merge Step, while merging two sorted halves, if arr[i] > arr[j], then all elements
after arr[i] in the left half will also be greater than arr[j], forming multiple inversions at

once.
Algorithm
1. Divide: Recursively divide the array into two halves.
2. Count left and right inversions using recursion.
3. Merge: While merging the two sorted halves, count cross inversions.
4. Return total count as sum of left, right, and cross inversions.
C++ Implementation
#include <iostream>
using namespace std;

int mergeAndCount(int arr[], int temp[], int left, int mid, int right) {
int i = left, j = mid, k = left, invCount = 0;

while (i <= mid - 1 && j <= right) {

if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
invCount += (mid - i); // Count inversions
}
}
while (i <= mid - 1) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];
for (i = left; i <= right; i++) arr[i] = temp[i];
return invCount;
}

int mergeSortAndCount(int arr[], int temp[], int left, int right) {

if (left >= right) return 0;
int mid = (left + right) / 2;
int invCount = mergeSortAndCount(arr, temp, left, mid);
invCount += mergeSortAndCount(arr, temp, mid + 1, right);
invCount += mergeAndCount(arr, temp, left, mid + 1, right);
return invCount;
}

49 BBN
int countInversionsMergeSort(int arr[], int n) {
int temp[n];
return mergeSortAndCount(arr, temp, 0, n - 1);
}

Complexity Analysis
 Merge Sort runs in O(N log N)
 Space Complexity = O(N) due to temporary array

Comparison of Approaches
Approach Time Complexity Space Complexity
Brute Force O(N^2) O(1)
Merge Sort O(N log N) O(N)

Knight's Tour Algorithm

Introduction
The Knight's Tour problem involves a knight on an N x N chessboard that must visit each square
exactly once. The knight moves in an L-shaped pattern: two squares in one direction and one
square perpendicular to it.

Possible Moves of a Knight

A knight at position (r, c) can move to the following eight possible positions:
1. (r - 2, c + 1)
2. (r - 1, c + 2)
3. (r + 1, c + 2)
4. (r + 2, c + 1)
5. (r + 2, c - 1)
6. (r + 1, c - 2)
7. (r - 1, c - 2)
8. (r - 2, c - 1)
Algorithm Approach

50 BBN
The algorithm uses backtracking to explore possible paths recursively. The main steps are:
1. Start at an initial position (0,0).
2. Mark the current square as visited.
3. Try all possible knight moves.
4. If a move leads to a solution, return true.
5. If not, backtrack and try a different move.
6. If all moves are exhausted and the tour is incomplete, return false.
Recursive Function
class Solution {
public:
bool isValid(vector<vector<int>>& grid,int r,int c,int expV,int n){
if(r<0||c<0||r>=n||c>=n||expV!=grid[r][c])return false;
if(expV==n*n-1)return true;
return isValid(grid,r+2,c+1,expV+1,n)||isValid(grid,r+2,c-1,expV+1,n)||
isValid(grid,r-2,c-1,expV+1,n)||isValid(grid,r-2,c+1,expV+1,n)||
isValid(grid,r+1,c+2,expV+1,n)||isValid(grid,r-1,c+2,expV+1,n)||isValid(grid,r-1,c-
2,expV+1,n)||isValid(grid,r+1,c-2,expV+1,n);
}
bool checkValidGrid(vector<vector<int>>& grid) {
return isValid(grid,0,0,0,[Link]());
}
};

Object-Oriented Programming (OOPs)

What is Object-Oriented Programming?
Object-Oriented Programming (OOPs) is a structured way of writing code that focuses on using
objects and classes. While OOPs is not mandatory for every program, it helps in writing clean,
organized, and scalable code. Companies and organizations prefer OOPs because it simplifies
code management and enhances reusability.
OOPs vs. Procedural Programming
In traditional procedural programming (e.g., writing C++ code without OOPs), we implement
logic in a sequential manner. However, using OOPs makes it easier to model real-world scenarios
into code, making programs more intuitive and maintainable.

Key Concepts of OOPs

1. Classes and Objects
 Class: A class is a blueprint or template that defines the properties and behaviors
(methods) of an object.
 Object: An object is an instance of a class that has specific values for its properties.
Example: Consider a car manufacturing company that creates different car models. The design
blueprint of a car (specifications) represents the class, while each manufactured car is an object
of that class.
2. Real-World Example: Teacher Management System
Imagine a college system where each teacher has specific information stored in a database. To
design this in C++ using OOPs, we need to:
 Define a Teacher class with properties such as name, department, subject, and salary.

51 BBN
  Implement methods (functions) like changeDepartment() or calculateTax(), which modify
or retrieve information about teachers.
 Use objects to store details of individual teachers.
class Teacher {
public:
string name;
string department;
string subject;
double salary;

void changeDepartment(string newDept) {

department = newDept;
}

double calculateTax() {
return salary * 0.1; // Example: 10% tax
}
};

Here, Teacher is the class, while individual teacher records will be objects created from this
class.
3. Implementation of OOPs in C++ STL
Many C++ libraries, such as vector, string, and stack, are implemented using OOPs concepts.
Learning how to create and use classes will help us understand and utilize these libraries
efficiently.
Access Modifiers
When studying classes and objects, defining properties and member functions is not
enough. We also need to specify their accessibility using access modifiers.
What are Access Modifiers?
Access modifiers are special keywords in C++ that define the accessibility of class members
(data and methods). There are three types of access modifiers:
1. Private
2. Public
3. Protected
1. Private Members
 Any data members (properties) or methods declared as private are only accessible
within the class.
 By default, all members of a class in C++ are private.
 Private members cannot be accessed outside the class, including in the main()
function.
 If we try to access a private member outside the class, it results in an error.
Example:
class Teacher {
private:
string name;
};

Here, name is private and cannot be accessed outside the class.

52 BBN
2. Public Members
 Any data members or methods declared as public are accessible both inside and
outside the class.
 Public members can be accessed in the main function or other classes.
Example:
class Teacher {
public:
string name;
};

Now, name can be accessed in the main() function.

3. Protected Members
 Protected members are similar to private members but with one key difference:
o They are accessible within the class.
o They are also accessible in derived (child) classes through inheritance.
 Private members do not get inherited, but protected members do.
Protected members are mainly useful when we study inheritance.
Example:
class Teacher {
protected:
double salary;
};

Here, salary is protected and can only be accessed inside this class and its derived classes.
Why Use Private Members?
In real-world applications, some data should not be accessible outside the class.
For example, in a college system, details like name, department, and subject can be public,
but salary should be private and accessible only by authorized users (e.g., the accounts
team).
Getter and Setter Functions
Since private members cannot be accessed directly, we use getter and setter functions to
access them.
 Setter function → Used to set (modify) a private variable.
 Getter function → Used to retrieve (get) a private variable.
Example:
class Teacher {
private:
double salary;

public:
void setSalary(double s) {
salary = s;
}

double getSalary() {
return salary;
}
};

53 BBN
Here, setSalary() is setting the salary value, and getSalary() is returning the value.
Encapsulation in OOP
 Encapsulation means binding data and methods together while restricting direct
access to the data.
 Private and protected access modifiers help achieve encapsulation.
 In interviews, encapsulation is one of the four key pillars of Object-Oriented
Programming (OOP):
1. Encapsulation
2. Abstraction
3. Inheritance
4. Polymorphism
Constructors in C++
When working with classes and objects, one important concept is the constructor. A
constructor is a special method that is automatically invoked whenever an object is created. It
is simple but plays a key role in initializing objects.
How Constructors Work
When an object is created, the constructor is called automatically.

It helps in allocating memory and initializing values to data members.

If a programmer does not define a constructor, C++ automatically provides a default

constructor.
Example:
class Teacher {
public:
Teacher() {
cout << "Hi, I am a constructor" << endl;
}
};

int main() {
Teacher t1; // Constructor is called automatically
Teacher t2; // Constructor is called again
}

Output:
Hi, I am a constructor
Hi, I am a constructor
 Every time an object (t1 or t2) is created, the constructor is invoked.
Why Use Constructors?
Automatic Initialization: Suppose all teachers in a school belong to the Computer

Science department. Instead of manually assigning the department to each teacher, we
can initialize it inside the constructor.
Example:
class Teacher {
public:
string department;

54 BBN
 Teacher() {
department = "Computer Science";
}
};

int main() {
Teacher t1;
cout << [Link]; // Output: Computer Science
}

Constructor Properties
1. Same Name as Class: The constructor function name must be identical to the class
name.
2. No Return Type: Constructors do not have a return type (not even void).
3. Automatically Invoked: They execute only once when an object is created.
Memory Allocation and Constructors
 Memory for an object is allocated only when the constructor is called.
Example:
class A {
int x;
};
o Memory is not allocated when a class is defined.
o Memory is allocated only when an object is created.
A obj1, obj2;
o obj1 and obj2 will get separate memory spaces for their variables.
Types of Constructors in C++
1. Default (Non-Parameterized) Constructor
o Does not take any arguments.
Example:
class A {
public:
A() {
cout << "Default Constructor Called" << endl;
}
};

2. Parameterized Constructor
o Takes arguments to initialize objects with custom values.
Example:
class Teacher {
public:
string name;
string department;

Teacher(string n, string d) {
name = n;
department = d;

55 BBN
 }
};

int main() {
Teacher t1("John", "Mathematics");
cout << [Link] << " - " << [Link];
}
Output:
John - Mathematics
3. Copy Constructor
o Creates a new object as a copy of an existing object.
Example:
class Teacher {
public:
string name;

Teacher(string n) {
name = n;
}

// Copy Constructor
Teacher(const Teacher &t) {
name = [Link];
}
};

int main() {
Teacher t1("Alice");
Teacher t2 = t1; // Copy constructor is called
cout << [Link]; // Output: Alice
}

Why Do We Need this Pointer?

 When using a parameterized constructor, we may want to use descriptive names for
variables instead of short names.
 For example, we may name variables as fullName, department, subject, salary, etc.
 However, if we assign values like name = name;, it creates confusion.
o The left-side name refers to the class property.
o The right-side name refers to the parameter.
How this Pointer Helps
 To remove confusion, we use the this pointer.
 this->name = name; means:
o this->name → refers to the object’s property.
o name → refers to the parameter passed to the constructor.
 Similarly, for other properties:
this->department = department;
this->salary = salary;
this->subject = subject;

56 BBN
 Using this ensures that the object's properties are properly assigned values from

the parameters.
How this Pointer Works
 Whenever an object is created, this stores the memory address of that object.
 Example: If an object t1 is created at memory location 100, this will store 100.
 this is an automatically created pointer that always points to the calling object.
Understanding Pointers for this
int x = 10;
int* ptr = &x;
 We can access x using either:
o x
o *ptr (dereferencing the pointer)
 Similarly, in this pointer:
o *this refers to the entire object.
o To access properties, we can use:
(*this).property
o Instead of this complex syntax, C++ provides a shortcut: this->property.
Copy Constructor in C++
 The copy constructor is used to copy properties from one object to another.
Teacher t1("John", "CS", "C++", 50000);
Teacher t2 = t1; // Calls the Copy Constructor
How It Works:
o When t2 is created using t1, C++ automatically invokes the default copy
constructor.
o It copies all properties of t1 into t2.
How Memory Works:
o If t1 has:
Name: John
Subject: C++
Department: CS
Salary: 50,000
o The memory is duplicated for t2, creating an exact copy.
Creating a Custom Copy Constructor
 We can manually define our own copy constructor:
class Teacher {
public:
string name, department, subject;
int salary;

// Copy Constructor
Teacher(const Teacher& t) {
name = [Link];
department = [Link];
subject = [Link];
salary = [Link];
}
};
 This ensures deep copying instead of relying on the default behavior.

57 BBN
Dynamic Memory Allocation
Dynamic memory allocation allows us to allocate memory at runtime using heap memory. It is
useful when we don’t know the exact size of memory needed beforehand.
Why use it?
 The size of memory is determined at runtime.
 More efficient use of memory compared to stack allocation.
How to allocate memory dynamically?
We use new in C++ to allocate memory and delete to free it.
Example:
#include <iostream>
using namespace std;

int main() {
int *ptr = new int; // Allocating memory dynamically
*ptr = 10; // Storing value in allocated memory

cout << "Value: " << *ptr << endl;

delete ptr; // Freeing memory

return 0;
}

For Arrays:
int *arr = new int[5]; // Allocating array dynamically
delete[] arr; // Free memory allocated for array

Copy Constructor
A copy constructor is used to create a new object as a copy of an existing object.
Why use it?
 It ensures proper copying when an object contains dynamically allocated memory.
 Default copy constructor performs shallow copy, which may lead to memory issues.
 We define a custom copy constructor for deep copy.
Shallow Copy (Default Copy Constructor)
#include <iostream>
using namespace std;

class Example {
public:
int *ptr;

Example(int val) {
ptr = new int(val);
}

void show() {
cout << "Value: " << *ptr << endl;
}
};

58 BBN
int main() {
Example obj1(10);
Example obj2 = obj1; // Default copy constructor (Shallow Copy)

[Link]();
[Link]();

return 0;
}

Problem with Shallow Copy in C++

A shallow copy only copies the pointer, not the actual memory. Multiple objects share the same
memory, leading to unexpected behaviour when one object modifies or deletes the memory.

Shallow Copy Issue Example

#include <iostream>
using namespace std;

class Example {
public:
int *ptr;

Example(int val) {
ptr = new int(val); // Allocating memory dynamically
}

// Default copy constructor (Shallow Copy)

Example(const Example &obj) {
ptr = [Link]; // Copying the pointer (Not allocating new memory)
}

void show() {
cout << "Value: " << *ptr << endl;
}

~Example() {
delete ptr; // Freeing memory (Problem occurs here)
}
};

int main() {
Example obj1(10);
Example obj2 = obj1; // Shallow Copy

[Link]();
[Link]();

delete [Link]; // Manually deleting obj1's memory

59 BBN
 [Link](); // Accessing deleted memory -> **Undefined Behavior (Crash)**

return 0;
}
Deep Copy (User-Defined Copy Constructor)
To avoid issues, we define a custom copy constructor that allocates new memory.
class Example {
public:
int *ptr;

Example(int val) {
ptr = new int(val);
}

// Custom copy constructor

Example(const Example &obj) {
ptr = new int(*[Link]); // Allocating new memory for deep copy
}

void show() {
cout << "Value: " << *ptr << endl;
}

~Example() {
delete ptr; // Free memory
}
};

int main() {
Example obj1(10);
Example obj2 = obj1; // Deep copy prevents shared memory issue

[Link]();
[Link]();

return 0;
}

Key Differences:
Feature Shallow Copy Deep Copy
Memory Allocation Same memory shared New memory allocated
Changes in One Affects Yes No
Another?
Custom Copy Constructor No Yes
Needed?

 Memory Allocation & Deallocation:

 Allocating memory means giving space to an object.

60 BBN
  A destructor is a special function that frees (deallocates) memory when an object is
no longer needed.
 If you don’t define a destructor, the compiler creates one automatically.
 The default destructor only frees statically allocated memory, not dynamically
allocated memory.
 Dynamic Memory & Destructor Problem:
 If an object contains dynamically allocated memory (using new), the default destructor
does not free it.
 This can cause a memory leak, where memory is wasted and not reused.
 Deleting Dynamic Memory:
 In C++, new is used to allocate memory, and delete is used to free it.
Example:
int* ptr = new int(55); // Allocating memory
delete ptr; // Freeing memory

delete ptr does not delete the pointer; it deletes the memory that the pointer was

pointing to.
 Example of Destructor:
#include <iostream>
using namespace std;

class Student {
public:
int* cgpa; // Pointer for dynamic memory

Student() {
cgpa = new int(10); // Allocating memory dynamically
cout << "Constructor: Memory allocated\n";
}

~Student() { // Destructor
delete cgpa; // Freeing allocated memory
cout << "Destructor: Memory freed\n";
}
};

int main() {
Student s1;
} // Destructor automatically called here

Output:
Constructor: Memory allocated
Destructor: Memory freed
 The constructor allocates memory dynamically.
 The destructor ensures that memory is properly freed.
 Why Destructors Are Important?
 In small programs, memory is automatically cleared when the program exits.

61 BBN
  In real-world applications (like company projects), properly freeing memory can cause
memory leaks and slow down the system.
 Memory Leak Example:
 If we forget to delete dynamically allocated memory:
void memoryLeak() {
int* num = new int(5); // Memory allocated
// No delete statement here → Memory leak!
}
 After calling memoryLeak(), the allocated memory remains occupied, wasting resources.

Inheritance
Inheritance in C++ is a way to pass properties from one class (parent class) to another class
(child class). There are three main types of inheritance modes:

1. Private Mode: If a class inherits another class in private mode, all public and protected
members of the parent class become private in the child class.
2. Protected Mode: If inheritance happens in protected mode, all public and protected
members of the parent class become protected in the child class.
3. Public Mode: In public mode, all public members of the parent class remain public in
the child class, and protected members remain protected.
Important Rules:
 Private members of the parent class are never inherited.
 The mode of inheritance decides how inherited properties behave inside the
child class.
Types of Inheritance:
1. Single Inheritance
A child class inherits from a single parent class.
class Person {
public:
string name;
int age;
};

class Student : public Person {

public:
int rollNumber;

62 BBN
};

2. Multi-level Inheritance
A class is inherited by another class, which is further inherited by a third class.
class Person {
public:
string name;
int age;
};

class Student : public Person {

public:
int rollNumber;
};

class GraduateStudent : public Student {

public:
string researchArea;
};

3. Multiple Inheritance
A child class inherits from multiple parent classes.
class Student {
public:
string name;
int rollNumber;
};

class Teacher {
public:
string subject;
double salary;
};

class TA : public Student, public Teacher {

// Teaching Assistant inherits from both Student and Teacher
};

4. Hierarchical Inheritance
Multiple child classes inherit from a single parent class.
class Person {
public:
string name;
int age;
};

class Student : public Person {

public:
int rollNumber;
};

63 BBN
class Teacher : public Person {
public:
string subject;
};

Polymorphism
What is Polymorphism?
Polymorphism is an important concept in Object-Oriented Programming (OOP). The word
"Polymorphism" comes from two Greek words:
 Poly means "many"
 Morph means "forms"
So, Polymorphism means the ability of an object to take multiple forms. It allows objects
to behave differently based on the context.
Example: Constructor Overloading
Constructor Overloading is a simple example of Polymorphism. It means defining multiple
constructors in the same class with different parameters.
Example Code:
#include<iostream>
using namespace std;

class Student {
public:
string name;

// Non-parameterized constructor
Student() {
cout << "Non-Parameterized Constructor Called" << endl;
}

// Parameterized constructor
Student(string n) {
name = n;
cout << "Parameterized Constructor Called" << endl;
}
};

int main() {
Student s1; // Calls Non-Parameterized Constructor
Student s2("Tony"); // Calls Parameterized Constructor
return 0;
}

Explanation:
 If no parameters are given → Non-Parameterized Constructor is called.
 If a name is provided → Parameterized Constructor is called.
Types of Polymorphism
1. Compile-time Polymorphism (Static Polymorphism)

64 BBN
 2. Run-time Polymorphism (Dynamic Polymorphism)

1. Compile-time Polymorphism
In Compile-time Polymorphism, the method to be executed is decided at compile-time.
Examples:
 Function Overloading
 Constructor Overloading
 Operator Overloading
Example: Function Overloading
Function Overloading means defining multiple functions with the same name but different
parameters.
Example Code:
#include<iostream>
using namespace std;

class Print {
public:
void show(int x) {
cout << "Integer: " << x << endl;
}
void show(char c) {
cout << "Character: " << c << endl;
}
};

int main() {
Print p;
[Link](10); // Calls show(int)
[Link]('A'); // Calls show(char)
return 0;
}

Explanation:
 The function show() is overloaded.
 If an integer is passed → show(int) is called.
 If a character is passed → show(char) is called.
Operator Overloading (Self-study)
Operators like +, =, * can be overloaded in C++ to work with user-defined data types.

2. Run-time Polymorphism (Dynamic Polymorphism)

Run-time Polymorphism is also called Dynamic Polymorphism because the method to be
executed is decided at run-time using method overriding.
Example: Method Overriding
Method Overriding occurs when a subclass provides a specific implementation of a method
already defined in its superclass.
Example Code:
#include<iostream>
using namespace std;

65 BBN
class Parent {
public:
virtual void show() {
cout << "Parent class show()" << endl;
}
};

class Child : public Parent {

public:
void show() override {
cout << "Child class show()" << endl;
}
};

int main() {
Parent* p;
Child c;
p = &c;
p->show(); // Calls Child class show() due to dynamic binding
return 0;
}

Explanation:
 The show() function in the parent class is declared as virtual, allowing dynamic binding.
 A pointer of type Parent points to an object of Child.
 At runtime, show() from Child is executed instead of Parent's show().
Key Differences Between Compile-time and Run-time Polymorphism
Feature Compile-time Polymorphism Run-time Polymorphism

Decision Time At compile-time At run-time

Mechanism Function overloading, operator overloading Method overriding, virtual functions

Performance Faster (resolved at compile-time) Slower (resolved at run-time)

Flexibility Less flexible More flexible

Additional Topics for Self-Study

 Virtual destructors
 Interfaces in C++
1. Access Modifiers and Abstraction
 Abstraction does not just mean hiding sensitive information; it also means displaying
important details.
Data Hiding vs. Abstraction:
o Data hiding means completely restricting access to certain information using
private members.
o Abstraction hides details while also exposing essential features.

66 BBN
  Access Modifiers (like public, private, protected) help in implementing abstraction by
controlling visibility.
2. Abstract Classes
If we prefix a class with abstract, it becomes an abstract class.

Abstract class: A class that serves as a blueprint but cannot be instantiated.

A normal class is used to create objects, whereas an abstract class is meant for

inheritance.
 Purpose of an Abstract Class:
o Defines a structure for other classes.
o Specifies which functions must be implemented in derived classes.
Example:
o A Shape class cannot be drawn because we don’t know what shape it is (circle,
square, etc.).
o The Shape class will have a draw() function, but we won’t implement it inside
Shape.
o Instead, Circle, Square, and Rectangle classes will inherit from Shape and
implement the draw() function accordingly.
3. Pure Virtual Functions
 A function that has no implementation in the base class and must be implemented in
derived classes.
Syntax:
class Shape {
public:
virtual void draw() = 0; // Pure virtual function
};
A class with at least one pure virtual function is an abstract class.
 Key Property:
o Abstract classes cannot have objects.
o Only derived classes can be instantiated.
4. Static Keyword
 The static keyword can be used with:
o Variables inside functions.
o Class members (variables and functions).
 Static Variable in a Function:
o Retains its value between function calls.
Example:
void fun() {
static int x = 0;
cout << x << endl;
x++;
}
If fun() is called three times, output will be:
0
1
2

67 BBN
Unlike normal variables, a static variable is created only once and persists throughout the
program.
5. Static Members in a Class
 Static Variables in a Class:
o Shared by all objects of the class.
o Example:
class Example {
static int count;
};

Static Functions in a Class:


o Can be called without creating an object.
o Cannot access non-static members directly.
Example:
class Example {
public:
static void show() {
cout << "Static function called";
}
};

Call it using:
Example::show();

Friend Function
What is a Friend Function?
A friend function is a function that is not a member of a class but has access to the private
and protected members of that class.
Why Use Friend Function?
 It helps access private data of a class without using member functions.
 It allows two or more classes to share data without inheritance.
 It is useful when overloading operators.
How to Declare a Friend Function?
Use the keyword friend inside the class.

The function definition is outside the class.

Example: Adding Two Numbers Using Friend Function
#include <iostream>
using namespace std;

class A {
private:
int num;

public:
A(int value) { num = value; }

// Declaring friend function

68 BBN
 friend int add(A obj1, A obj2);
};

// Friend function definition

int add(A obj1, A obj2) {
return [Link] + [Link];
}

int main() {
A obj1(5), obj2(10);
cout << "Sum: " << add(obj1, obj2) << endl;
return 0;
}

Output:
Sum: 15

Linked List
Introduction to Linked List
A Linked List is a dynamic data structure used for storing a collection of elements. Unlike
arrays, linked lists allow efficient insertions and deletions without requiring memory reallocation.
Advantages of Linked List:
 Dynamic size: No need to define size beforehand.
 Efficient Insertions/Deletions: Operations like insertions and deletions are faster than
arrays as elements are linked using pointers.
 Memory Utilization: No memory wastage due to pre-allocation.
Types of Linked List:
1. Singly Linked List: Each node points to the next node in the list.
2. Doubly Linked List: Each node contains pointers to both the next and previous nodes.
3. Circular Linked List: The last node points back to the first node.

Implementation of Singly Linked List in C++

Node Structure
Each node consists of two parts:
1. Data - Stores the value.
2. Pointer - Holds the address of the next node.
#include <iostream>
using namespace std;

// Node structure
class Node {
public:
int data;
Node* next;

Node(int val) {
data = val;

69 BBN
 next = nullptr;
}
};

Linked List Class

We define a LinkedList class that contains methods to perform various operations:
class LinkedList {
private:
Node* head;
public:
LinkedList() { head = nullptr; }

// Insert a node at the end

void insert(int val) {
Node* newNode = new Node(val);
if (head == nullptr) {
head = newNode;
return;
}
Node* temp = head;
while (temp->next != nullptr) {
temp = temp->next;
}
temp->next = newNode;
}

// Delete a node by value

void deleteNode(int val) {
if (head == nullptr) return;
if (head->data == val) {
Node* temp = head;
head = head->next;
delete temp;
return;
}
Node* temp = head;
while (temp->next != nullptr && temp->next->data != val) {
temp = temp->next;
}
if (temp->next == nullptr) return;
Node* toDelete = temp->next;
temp->next = temp->next->next;
delete toDelete;
}

// Display the linked list

void display() {
Node* temp = head;
while (temp != nullptr) {
cout << temp->data << " -> ";
temp = temp->next;

70 BBN
 }
cout << "NULL" << endl;
}
};

Main Function
int main() {
LinkedList list;
[Link](10);
[Link](20);
[Link](30);

cout << "Linked List: ";

[Link]();

[Link](20);
cout << "After deletion: ";
[Link]();

return 0;
}

Explanation of Operations
1. Insertion
 Creates a new node.
 If the list is empty, sets the new node as head.
 Otherwise, traverses to the last node and appends the new node.
2. Deletion
 If the node to be deleted is the head, moves head to the next node and deletes the
original head.
 Otherwise, finds the node before the target node, updates its next pointer, and deletes the
target node.
3. Traversal (Display)
 Starts from head and moves through each node, printing its data until reaching nullptr.

Time Complexity
Operation Time Complexity

Insertion O(n) (at end)

Deletion O(n)

Traversal O(n)

Reverse a Linked List

71 BBN
Problem Statement
We are given a linked list, and our task is to reverse it. This problem is listed as Problem No.
206 on LeetCode.
The linked list structure is already provided, with each node having:
 A value
 A next pointer
 Predefined constructors
We need to complete the function reverseList(), which takes the head of the linked list as input
and returns the head of the reversed linked list.
Example
Before Reversing:
1 -> 2 -> 3 -> 4 -> 5 -> NULL
After Reversing:
5 -> 4 -> 3 -> 2 -> 1 -> NULL
Only the connections between nodes change; node values remain the same.
Approach to Solve the Problem
To solve this problem, we use a standard approach that involves pointer manipulation. The
idea is to change the direction of links so that the last node becomes the new head.
Steps to Reverse a Linked List
We use three pointers:
1. Previous (prev): Points to the previous node
2. Current (curr): Points to the current node
3. Next (next): Helps in tracking the next node
Process:
1. Initialize pointers:
o prev = NULL
o curr = head
o next = NULL
2. Iterate through the linked list:
o Store the next node: next = curr->next
o Reverse the link: curr->next = prev
o Move the pointers:
 prev = curr
 curr = next
3. Repeat these steps until curr becomes NULL.
4. Return prev as the new head of the reversed list.
Key Observations
 The last node of the original list becomes the new head.
 We carefully preserve the next node before reversing the link to prevent data loss.
 The process stops when curr becomes NULL.
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head==NULL)return head;
ListNode* prev=NULL;
ListNode* next=head->next;

72 BBN
 while(next!=NULL){
head->next=prev;
prev=head;
head=next;
next=head->next;
}
head->next=prev;
return head;
}
};

Find the Middle of a Linked List

Problem Statement
We are given a linked list, and we need to find and return its middle node:
 If the list has an odd number of nodes → Return the exact middle node.
 If the list has an even number of nodes → Return the second middle node.
💡 This problem is LeetCode Question #876

Example Cases
Example 1 (Even-sized list)
📌 Linked List: 1 → 2 → 3 → 4 → 5 → 6
✅ Middle Node: 4 (since 4 is the second middle node in an even-sized list)
Example 2 (Odd-sized list)
📌 Linked List: 1 → 2 → 3 → 4 → 5
✅ Middle Node: 3 (since 3 is exactly in the middle)

Slow and Fast Pointer (Optimal Method)

We use two pointers:
 Slow Pointer (moves 1 step at a time)
 Fast Pointer (moves 2 steps at a time)
Steps to solve using this approach
1️Initialize both slow and fast pointers at the head.
2️Move slow by 1 step and fast by 2 steps in each iteration.
3️When fast reaches the end (or null), slow will be at the middle node.
4️Return the slow pointer as the middle node.
⏳ Time Complexity: O(N) (only one pass)
📌 Space Complexity: O(1) (no extra space used)

Example Execution (Slow & Fast Pointer Method)

Even-sized List (1 → 2 → 3 → 4 → 5 → 6)
Step Slow Pointer Fast Pointer
Start 1 1
Move 1 2 3
Move 2 3 5

73 BBN
 Step Slow Pointer Fast Pointer
Move 3 4 null
✅ Middle Node Found: 4
Odd-sized List (1 → 2 → 3 → 4 → 5)
Step Slow Pointer Fast Pointer
Start 1 1
Move 1 2 3
Move 2 3 5
Move 3 null null
✅ Middle Node Found: 3

class Solution {
public:
ListNode* middleNode(ListNode* head) {
ListNode* slow=head;
ListNode* fast=head;
while(fast!=NULL&&fast->next!=NULL){
fast=fast->next->next;
slow=slow->next;
}
return slow;
}
};

Why Use Slow & Fast Pointer?

✅ More Efficient (Only one pass instead of two)
✅ No need to calculate the size of the list
✅ Used in many linked list problems (e.g., cycle detection, palindrome check, etc.)

Merge Two Sorted Lists

Problem Statement
This problem, "Merge Two Sorted Lists" (Problem No. 21 on LeetCode), provides a
function that we need to complete. The
structure of the linked list is already
defined.

The function, mergeTwoLists, takes two

sorted linked lists as input, with their
respective head nodes given (h1 and h2).
The goal is to merge these two sorted
linked lists into one sorted list and return
the head of the final merged list.
Approach to Solve the
Problem

74 BBN
To solve this problem, we will use recursion. Many Linked List problems are easier to solve
using recursion rather than an iterative approach. Recursive solutions are often simpler and
more intuitive in such cases.
Understanding Recursion
Whenever we write a recursive function, we do not focus on solving the entire problem at once.
Instead, we break the larger problem into a smaller, simpler problem.
The big problem in this problem is merging two sorted linked lists. However, the small
problem is determining the head node for the merged list at each recursion level.
Steps to Solve Recursively:
1. If both lists are non-empty, compare the head nodes (h1 and h2).
2. The smaller node will become the head of the new merged list.
3. The remaining part of the linked list will be merged recursively.
4. Return the merged list.
Recursive Logic
At each step, we compare h1 and h2:
1. Case 1: If h1->val <= h2->val, h1 becomes the head.
o Recursively merge h1->next with h2.
o Set h1->next to the result of the recursive call.
o Return h1.
2. Case 2: If h1->val > h2->val, h2 becomes the head.
o Recursively merge h1 with h2->next.
o Set h2->next to the result of the recursive call.
o Return h2.
Base Condition
 If either list is empty, return the non-empty list as the merged result.
Implementation

class Solution {
public:

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {

if(l1==nullptr)return l2;
if(l2==nullptr)return l1;
if((l1->val) <=l2->val){
l1->next=mergeTwoLists(l1->next,l2);
return l1;
}
else{
l2->next=mergeTwoLists(l1,l2->next);
return l2;
}

}
};
Complexity Analysis
 Time Complexity: O(N + M), where N and M are the lengths of the two lists.
 Space Complexity: O(N + M) due to recursive stack space.

75 BBN
Deep Copy of a Linked List with Random Pointers
Understanding the Problem

A linked list of length n is given such that each node contains an additional random pointer, which
could point to any node in the list, or null.

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes,
where each new node has its value set to the value of its corresponding original node. Both
the next and random pointer of the new nodes should point to new nodes in the copied list such that
the pointers in the original list and copied list represent the same list state. None of the pointers in
the new list should point to nodes in the original list.

For example, if there are two nodes X and Y in the original list, where [Link] --> Y, then for the
corresponding two nodes x and y in the copied list, [Link] --> y.

Return the head of the copied linked list.

The linked list is represented in the input/output as a list of n nodes. Each node is represented as a
pair of [val, random_index] where:

 val: an integer representing [Link]

 random_index: the index of the node (range from 0 to n-1) that the random pointer points to,
or null if it does not point to any node.

Your code will only be given the head of the original linked list.

Example Representation

76 BBN
Problem Breakdown
 This is LeetCode problem 138.
 We need to implement a function that receives the head of the given linked list and
returns the head of its deep copy.
Approach to Solve the Problem
We solve this problem in two steps:
Step 1: Create a Simple Copy of the Linked List
 Ignore the random pointers for now.
 Simply copy each node and maintain the next connections as in the original list.
 The copied linked list will follow the same sequence as the original, but without any
random pointer connections.
Step 2: Copy the Random Pointer Connections
 Iterate through the original list again.
 Assign the corresponding random pointers from the original list to the copied list.
Step-by-Step Execution
1. Creating a Simple Copy
o Initialize old_temp to point to the head of the original linked list.
o Create a new_head which is a copy of the first node.
o Maintain two pointers:
 old_temp: Traverses the original list.
 new_temp: Traverses the newly created list.
o For each node in the original list:
 Create a copy node with the same value.
 Set new_temp.next = copy_node.
 Move old_temp and new_temp to their respective next nodes.

77 BBN
 o Repeat until old_temp reaches NULL.
class Solution {
public:
Node* copyRandomList(Node* head) {
if(head==nullptr)return nullptr;
Node* newHead=new Node(head->val);
unordered_map<Node*,Node*> m;
Node* oldtemp=head->next;
Node* newtemp=newHead;
m[head]=newHead;
while(oldtemp!=nullptr){
Node* newNode=new Node(oldtemp->val);
m[oldtemp]=newNode;
newtemp->next=newNode;
newtemp=newtemp->next;
oldtemp=oldtemp->next;
}
newtemp->next=nullptr;
newtemp=newHead;
oldtemp=head;
while(oldtemp!=nullptr){
newtemp->random=m[oldtemp->random];
oldtemp=oldtemp->next;
newtemp=newtemp->next;
}
return newHead;
}
};

2. Copying the Random Pointers

o Iterate through the original and copied lists simultaneously.
o Assign new_temp.random = old_temp.random.
o Move both pointers to their respective next nodes.
o Repeat until old_temp reaches NULL.

Final Output
 The copied list should have nodes with the same values and connections as the original.
 The next and random pointers should correctly replicate those of the original list.
 The function returns the head of the copied linked list.

Doubly Linked List

Before understanding DLL, let's recall Singly
Linked List (SLL):
 Each node stores data and a pointer to
the next node.
 The last node points to NULL.

Now, in Doubly Linked List (DLL):

78 BBN
Structure of a Doubly Linked List Node
Each node in a DLL contains:
1. Data (stores information)
2. Next pointer (points to the next node)

3. Previous pointer (points to the previous node)

Head Node: prev is NULL (no previous node).
Tail Node: next is NULL (no next node).

Implementation of Doubly Linked List

To implement a Doubly Linked List, we need:
1. Node class (to create individual nodes)
2. Doubly Linked List class (to manage the list)
1. Node Class
 Each node has:
o data
o next pointer
o prev pointer
 The constructor initializes:
o data = given value
o next = NULL
o prev = NULL
class Node
{
public:
int data;
Node *next;
Node *prev;
Node(int data)
{
this->data = data;
next = prev = nullptr;
}
};

2. Doubly Linked List Class

79 BBN
  Contains:
o head (starting node)
o tail (last node)
 Constructor initializes:
o head = NULL
o tail = NULL
class Doubly
{
Node *head;
Node *tail;

public:
Doubly()
{
head = tail = nullptr;
}

Functions in Doubly Linked List

1. Insertion (Add a new node)
void push_front(int val)
{
Node *newNode = new Node(val);
if (head == nullptr)
{
head = tail = newNode;
return;
}
newNode->next = head;
head->prev = newNode;
head = newNode;
}

void push_back(int val)

{
Node *newN = new Node(val);
if (head == nullptr)
{
head = tail = newN;
return;
}
tail->next = newN;
newN->prev = tail;
tail = newN;
}

2. Deletion (Remove a node)

void pop_front()

80 BBN
 {
if (head == nullptr)
{
cout << "Empty list" << endl;
return;
}
Node *temp = head;
head = head->next;
if (head == nullptr)
{
tail = nullptr;
}
else
{
head->prev = nullptr;
}

delete temp;
}

void pop_back()
{
if (head == nullptr)
{
cout << "Empty list." << endl;
return;
}
Node *temp = tail;
tail = tail->prev;
if (tail == nullptr)
{
head = nullptr;
}
else
{
tail->next = nullptr;
}
delete temp;
}

3. Traversal (Print the list)

void print()
{
cout << "NULL <--- ";
Node *temp = head;
while (temp != nullptr)
{
if (temp->next == NULL)
{
cout << temp->data;
}

81 BBN
 else
{
cout << temp->data << " <---> ";
}

temp = temp->next;
}
cout << " ---> NULL" << endl;
}

4. Search (Find an element)

Implement by self.
5. Reverse (Reverse the list)
Implement by self.
These functions help in managing a Doubly Linked List efficiently.

Circular Linked List

The main difference in a circular linked list is that the tail’s next pointer does not point to
NULL.
 Instead, it points back to the head node,
forming a circular structure.
 This allows traversal to continuously cycle
through the list.
Circular Linked List Implementation
 Unlike normal linked lists, a circular linked list
does not necessarily require a head pointer.
 The tail pointer alone is enough for
implementation because:
o The head can always be accessed using
tail->next (since tail connects to head).
4. Advantages of Circular Linked Lists
 Efficient Insertion: Inserting at the head is easy, as we just need to update the tail’s
next pointer.
 No NULL Reference: Unlike normal lists, there is no NULL in the list, making operations
easier in certain applications.
 Continuous Traversal: Since the list is circular, traversal never ends unless explicitly
stopped.
5. Common Questions in DSA & Placements
 Most placement questions are based on:
o Singly linked lists
o Doubly linked lists
o Circular linked lists (asked less frequently but important to understand
conceptually)
6. Structure of Circular Linked List in C++
 A Node class is created with:
o An integer data field.

82 BBN
 o A next pointer pointing to the next node.
 A Circular List class contains:
o A head pointer (optional).
o A tail pointer (important for easy insertion).
7. Creating a Circular Linked List in C++
 First, define a Node class with:
o A constructor initializing data and next.
 Define a CircularLinkedList class with:
o Head and tail pointers initialized to NULL.
#include <iostream>
using namespace std;

class Node
{
public:
int val;
Node *next;
Node(int val)
{
this->val = val;
next = nullptr;
}
};

class Circular
{
Node *head;
Node *tail;

public:
Circular()
{
head = tail = nullptr;
}
void push_front(int val)
{
Node *newNode = new Node(val);
if (head == nullptr)
{
head = tail = newNode;
}
else
{
newNode->next = head;
head = newNode;
}
tail->next = head;
}

void push_back(int val)

83 BBN
 {
Node *newNode = new Node(val);
if (head == nullptr)
{
head = tail = newNode;
}
else
{
tail->next = newNode;
tail = newNode;
}
tail->next = head;
}

void pop_front()
{
if (head == nullptr)
{
cout << "Empty list.";
return;
}
Node *temp = head;
if (head == tail)
{
head = tail = nullptr;
}
else
{
head = head->next;
tail->next = head;
}
delete temp;
}

void pop_back()
{
if (head == nullptr)
{
cout << "Empty list.";
return;
}
Node *temp = head;
if (head == tail)
{
delete temp;
head = tail = nullptr;
return;
}

while (temp->next != tail)

{

84 BBN
 temp = temp->next;
}
delete tail;
tail = temp;
tail->next = head;
}
void print()
{
if (head == nullptr)
return;
Node *temp = head;
do
{
cout << temp->val << " ---> ";
temp = temp->next;
} while (temp != head);
cout << head->val << endl;
}
};
int main()
{
Circular cl;
cl.push_front(2);
// cl.push_back(4);
// cl.push_back(6);
[Link]();
cl.pop_back();
// cl.pop_back();

[Link]();
return 0;
}

Flattening a Linked List Using Recursion

Understanding the Problem
We are given a function where the head of a linked list is provided. Our goal is to flatten the
linked list and return the head of the flattened list.
Steps to Solve the Problem Using Recursion
1. Initialize Pointers:
o Start with the head of the linked list.
o Create a pointer called current and initialize it with head.
2. Traverse the Linked List:
o Use a loop to traverse through each node until current becomes NULL.
o If the current node has no child, move to the next node.
o If a child node exists, handle it using recursion.
3. Handling Child Nodes:
o If a node has a child, we need to flatten the entire child linked list first.

85 BBN
 Call the recursive function on the child node, which will return the flattened child
o
list’s head.
o Store current->next in a temporary pointer (nextPointer) before modifying any
connections.
o Update current->next to point to the flattened child list.
4. Maintain Double-Linking:
o Since it's a doubly linked list, update the previous pointer of the first node in the
flattened child list to point back to current.
o Connect the last node of the flattened child list to nextPointer (if it exists).
5. Repeat Until Fully Flattened:
o Move current to the next node and repeat the process until the entire linked list is
flattened.
Recursive Thought Process
Recursion works on breaking the problem into smaller parts and solving each part independently.
 If recursion can flatten a large linked list, it can also flatten a smaller child list.
 We trust the recursive function to flatten the child list for us.
 Once we receive the flattened child list’s head, we merge it into the main list.
Final Steps
1. Store current->next in nextPointer.
2. Call the recursive function on the child list.
3. Update current->next to point to the flattened child list.
4. Ensure the previous pointer is updated in the doubly linked list.
5. Finally, connect the last node of the flattened child list to nextPointer.
class Solution {
public:
Node* flatten(Node* head) {
if(head==nullptr)return nullptr;

Node* curr=head;
while(curr!=nullptr){
if(curr->child!=nullptr){
Node* next=curr->next;
curr->next=flatten(curr->child);
curr->next->prev=curr;
curr->child=nullptr;

while(curr->next!=nullptr){
curr=curr->next;
}
if(next!=nullptr){
curr->next=next;
next->prev=curr;
}
}
curr=curr->next;
}
return head;
}

86 BBN
 };

Reversing K-Group Nodes in a Linked List Using

Recursion
Concept Overview
To reverse nodes in a linked list in groups of size K, we follow a recursive approach. Instead of
reversing all K-group nodes at once, we reverse a particular K-group and recursively solve the
remaining linked list.
Recursion works on the principle that if a function can solve a big problem, then calling the same
function for a smaller part of the problem will also work.
Thus, if our recursive function can reverse all K-groups in the entire linked list, we can trust that
reversing one K-group at a time will eventually solve the whole problem.
Approach to Solving the Problem
We will divide the problem into three major steps:
1. Check if K nodes exist in the current group
2. Recursively reverse the rest of the linked list
3. Reverse the current K-group and connect it to the reversed rest of the linked list
Step 1: Checking If K Nodes Exist
Before reversing any K-group, we first check whether there are at least K nodes in the current
segment. If not, we return the linked list as it is.
Example: If we have a linked list:
1 -> 2 -> 3 -> 4 -> 5
and K = 2, we need to ensure that at least 2 nodes exist before attempting to reverse them.
To check for K nodes:
 Use a temporary pointer starting from the head.
 Traverse the list while keeping a count.
 If the count reaches K, we proceed to the next step.
 If the pointer reaches NULL before counting K nodes, we return the linked list as it is.
Step 2: Recursively Reverse the Rest of the Linked List
Once we confirm that K nodes exist in the current group, we assume that the remaining linked
list will be reversed by the recursive function.
Example: If we have the linked list:
1 -> 2 -> 3 -> 4 -> 5
and we call the function on 4 -> 5, we assume it will return:
5 -> 4
This assumption allows us to focus only on reversing the current K-group.
Step 3: Reversing the Current K-Group
To reverse a group of K nodes:
1. The first node in the group moves to the end.
2. Each node shifts its pointer to the previous node in the group.
3. The last node in the group becomes the new head.
4. Connect this reversed group to the reversed rest of the linked list.

87 BBN
Example: If we have 1 -> 2 -> 3 -> 4 -> 5 with K=3, after reversing the first K-group, it
becomes:
3 -> 2 -> 1 -> 4 -> 5
Then, we connect this to the reversed rest of the linked list.
Implementation Logic
1. Create a function reverseKGroup(head, K).
2. Check if at least K nodes exist.
3. Reverse the first K nodes.
4. Call reverseKGroup() on the remaining linked list.
5. Connect the reversed group to the reversed remainder.
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
if (head == nullptr) return nullptr;

// Check if there are at least k nodes to reverse

ListNode* temp = head;
int count = 0;
while (count < k) {
if (temp == nullptr) return head; // Not enough nodes, return head as
is
temp = temp->next;
count++;
}
// Recursively reverse the next k-group and connect it to the current reversed
list
ListNode* prev = reverseKGroup(temp, k);
// Reverse first k nodes
ListNode* curr = head;
ListNode* next = nullptr;
count = 0;
while (count < k) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
count++;
}

// `prev` is now the new head of the reversed k-group

return prev;
}
};

Complexity Analysis
 Time Complexity: O(N) as each node is visited once and reversed once.
 Space Complexity: O(N/K) due to recursive calls (stack space).

88 BBN
Example Execution
Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6, K=3
Output: 3 -> 2 -> 1 -> 6 -> 5 -> 4

Stacks
What is a Stack?
A stack is a data structure that follows the LIFO (Last In, First Out) rule. This means the last
item you add is the first one you remove. Think of a stack of plates—when you add a new plate,
it goes on top, and when you take one, you remove the top plate first.
Operations in a Stack
1. Push → Add an element to the top of the stack.
2. Pop → Remove the top element from the stack.
3. Peek (or Top) → View the top element without removing it.
4. isEmpty → Check if the stack is empty.
5. Size → Get the number of elements in the stack.
Example of a Stack
Imagine you have a stack of books:
 You add books one by one (Push).
 You remove the top book first (Pop).
 You check which book is on top without
removing it (Peek).
Implementation of a Stack
Stacks can be implemented in:
 Vectors (dynamic size, faster access)
#include <iostream>
#include <vector>
using namespace std;

class Stack {
private:
vector<int> v;

public:
void push(int val) { v.push_back(val); } // Add element
void pop() { if (![Link]()) v.pop_back(); } // Remove top
int top() { return [Link]() ? -1 : [Link](); } // Return top element
bool empty() { return [Link](); } // Check if empty
};

int main() {
Stack s;
[Link](10);
[Link](20);
[Link](30);
while (![Link]()) {
cout << [Link]() << " "; // Print top
[Link](); // Remove top

89 BBN
 }
return 0;
}

📝 Output
30 20 10
 Linked Lists (dynamic size, uses more memory)
#include <iostream>
using namespace std;

class Node {
public:
int data;
Node* next;
Node(int val) { data = val; next = NULL; }
};

class Stack {
private:
Node* head;

public:
Stack() { head = NULL; }

void push(int val) {

Node* newNode = new Node(val);
newNode->next = head;
head = newNode;
}

void pop() {
if (head != NULL) {
Node* temp = head;
head = head->next;
delete temp;
}
}

int top() {
return head == NULL ? -1 : head->data;
}

bool empty() {
return head == NULL;
}
};

int main() {
Stack s;
[Link](10);
[Link](20);

90 BBN
 [Link](30);

while (![Link]()) {
cout << [Link]() << " ";
[Link]();
}
return 0;
}

📝 Output
30 20 10

🔍 Key Differences Between Vector & Linked List Stack

Feature Vector Stack Linked List Stack

Uses dynamic array (more memory needed Uses nodes (extra memory for
Memory Usage
for resizing) pointers)

Push
O(1) (most cases), O(N) if resizing is needed O(1) always
Complexity

Pop Complexity O(1) O(1)

Access Speed Faster (stored in contiguous memory) Slower (scattered in memory)

Size Limitation No fixed limit (depends on RAM) No fixed limit

Stack Applications
1. Undo/Redo in text editors.
2. Back/Forward in web browsers.
3. Expression evaluation (like checking balanced parentheses).
4. Recursion (function calls use stacks).

📌 Valid and Invalid Parentheses Using Stack

What is a Valid Parentheses String?
A valid parentheses string follows a rule where:
 Every opening bracket ((, {, [) has a matching closing bracket (), }, ]).
 The order of brackets should be correct.
 The last opened bracket should be the first to close (LIFO order → Last In, First
Out).
For example:
✅ "({[]})" → This is valid because the brackets are properly nested and closed in the correct
order.

91 BBN
What is an Invalid Parentheses String?
A string is invalid when:
 A closing bracket appears without a matching opening bracket.
 The order of brackets is incorrect.
 Extra opening brackets exist without a closing pair.
Examples:
❌ "{[}]" → The { does not close correctly before ].
❌ "({[})]" → The { is closed before the [ is closed, which is incorrect.
❌ "(((" → There are three opening brackets but no closing brackets.

How to Identify a Valid or Invalid String? (General Rule)

A valid string always follows this pattern:
 The closing brackets appear in reverse order of their corresponding opening
brackets.
 Example:
o Opening order → "({["
o Closing order → "]})" (reverse of the opening order).
o Since they close in the correct sequence, the string is valid.
If the brackets do not close in reverse order, then the string is invalid.

Using Stack Data Structure to Check Valid Parentheses

A stack helps in solving this problem because it follows the LIFO (Last In, First Out) rule.
How does it work?
1️⃣ If we encounter an opening bracket, we push it into the stack.
2️⃣ If we encounter a closing bracket, we check the top of the stack:
 If the top has the matching opening bracket, we pop it from the stack.
 If it doesn’t match or the stack is empty, the string is invalid.
3️⃣ After scanning the entire string, if the stack is empty, the string is valid. Otherwise, it's
invalid.

Example Walkthrough (Step-by-Step Using Stack)

Let's check if "({[]})" is a valid string.
Step 1: Process Each Character
Character Stack Action Stack Content
( Push to stack (
{ Push to stack ({
[ Push to stack ({[
] Matches [ → Pop ({
} Matches { → Pop (
) Matches ( → Pop Empty
✔ Final Stack = Empty → The string is valid ✅.

92 BBN
When Does a String Become Invalid?
Let's check "({[}])" step by step.
Characte Stack
Stack Action
r Content
( Push to stack (
{ Push to stack ({
[ Push to stack ({[
} ❌ Mismatch! Expected ], found { Invalid
❌ Stack mismatch occurs → The string is invalid.

Special Cases to Handle

✅ If a closing bracket comes before an opening bracket, it's invalid.
✅ If the stack is empty before all brackets are matched, it's invalid.
✅ If the stack still has leftover opening brackets after processing, it's invalid.

C++ Code to Check Valid Parentheses

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

bool isValid(string s) {
stack<char> st;
for (char c : s) {
if (c == '(' || c == '{' || c == '[') {
[Link](c); // Push opening brackets
} else {
if ([Link]()) return false; // No matching opening bracket

char top = [Link]();

if ((c == ')' && top == '(') ||
(c == '}' && top == '{') ||
(c == ']' && top == '[')) {
[Link](); // Match found, remove it
} else {
return false; // Mismatch
}
}
}
return [Link](); // Stack should be empty if valid
}

int main() {
string test = "({[]})";
cout << (isValid(test) ? "Valid" : "Invalid") << endl;
return 0;
}

93 BBN
Stock Span Problem?
The Stock Span Problem is a financial problem where we calculate how many consecutive
days before today had a price lower than or equal to today’s price.
For example, if today’s stock price is 70, we count how many previous days had prices
lower than or equal to 70.
✅ Example:
Stock Prices: [100, 80, 60, 70, 60, 75, 85]
Stock Span: [1, 1, 1, 2, 1, 4, 6]
 Day 0 (100) → No previous lower prices → Span = 1
 Day 1 (80) → No previous lower prices → Span = 1
 Day 2 (60) → No previous lower prices → Span = 1
 Day 3 (70) → 60 is lower → Span = 2 (includes itself)
 Day 4 (60) → No previous lower prices → Span = 1
 Day 5 (75) → 60, 70, and 60 are lower → Span = 4
 Day 6 (85) → 75, 60, 70, 60 are lower → Span = 6

How to Calculate the Stock Span?

To calculate the span for each day i, we check how many consecutive previous days had
prices lower than or equal to stock[i].
Naive Approach (Brute Force)
 For each day i, look back at previous days and count the span.
 Time Complexity: O(N²) (not efficient for large inputs).
Efficient Approach Using Stack
 Instead of checking all previous prices manually, we store previous larger elements in
a stack.
 Time Complexity: O(N) (much faster).

Understanding the Stack-Based Approach

What does the stack store?
 The index of the previous greater stock price.
How does it work?
1️⃣ If the stack is empty, that means all previous stock prices were smaller → Span = i + 1.
2️⃣ If the stack has elements, we check:
 If stock[[Link]()] < stock[i], we remove elements from the stack because they are
useless.
 The new top of the stack will be the nearest previous greater stock.
 Span = i - [Link]().

Step-by-Step Example Using Stack

Stock Prices: [100, 80, 60, 70, 60, 75, 85]
Day Price Stack (Indexes) Span Calculation Final Span

0 100 [0] i+1=1 1

1 80 [0, 1] i - [Link]() = 1 1

94 BBN
Day Price Stack (Indexes) Span Calculation Final Span

2 60 [0, 1, 2] i - [Link]() = 1 1

3 70 [0, 1] (pop 2) i - [Link]() = 3 - 1 = 2 2

4 60 [0, 1, 4] i - [Link]() = 1 1

5 75 [0, 1] (pop 4, 3) i - [Link]() = 5 - 1 = 4 4

6 85 [0] (pop 5, 1) i - [Link]() = 6 - 0 = 6 6

✅ Final Span Array: [1, 1, 1, 2, 1, 4, 6]

C++ Code for Stock Span Problem

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

vector<int> StockSpan(vector<int> &stock) {

stack<int> s;
vector<int> span([Link](), 0);

for (int i = 0; i < [Link](); i++) {

while (![Link]() && stock[[Link]()] <= stock[i]) {
[Link]();
}

if ([Link]()) {
span[i] = i + 1; // No previous greater element
} else {
span[i] = i - [Link](); // Distance from nearest greater element
}

[Link](i); // Store index of the current price

}
return span;
}

int main() {
vector<int> nums = {100, 80, 60, 70, 60, 75, 85};
vector<int> span = StockSpan(nums);

for (int s : span) {

cout << s << " ";
}
}

Why is This Approach Efficient?

 Brute Force: Checks all previous elements for each stock → O(N²)

95 BBN
 Stack Approach: Each element is pushed & popped at most once → O(N)
✅ Stack ensures efficient lookup of previous greater elements.

Next Greater Element Using Stack

The next greater element of some element x in an array is the first greater element that is to
the right of x in the same array.

You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset
of nums2.

For each 0 <= i < [Link], find the index j such that nums1[i] == nums2[j] and determine the next
greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this
query is -1.

Return an array ans of length [Link] such that ans[i] is the next greater element as described
above.

Example 1:

Input: nums1 = [4,1,2], nums2 = [1,3,4,2]

Output: [-1,3,-1]

Explanation: The next greater element for each value of nums1 is as follows:

- 4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.

- 1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3.

- 2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.

Why Do We Use a Stack?

For any given element, say 6, we need two key pieces of information:
1. Which elements exist on its right side?
2. Which of those elements are greater than 6?
If we can track these values efficiently, we can determine the Next Greater Element, as that is
its literal definition.
Naive Approach vs. Optimized Approach
A naive way to solve this problem is by using a forward loop for every element to find its next
greater element. However, this approach has a high time complexity.
Instead, we use a reverse approach with a stack for efficiency.
Why Reverse Traversal?
 The last element of the array does not have any elements on its right, so its Next
Greater Element is always -1.
 As we move backward, we already have information about the elements on the right.
How Does the Stack Help?

96 BBN
  We store elements in a stack because we need to maintain the order of the next greater
elements in reverse order.
 The stack helps us track the immediate greater element efficiently.
 Since a stack follows LIFO (Last In, First Out), the most recent element will always be
on top, making it easy to access.
Implementation Strategy
1. Start from the rightmost element and move toward the left.
2. Use a stack to store potential Next Greater Elements.
3. For each element:
o Pop elements from the stack until we find a greater element.
o If no greater element exists, store -1.
o Push the current element onto the stack so it can be used for future elements.
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
//find next Greater Element for nums2
unordered_map<int,int> m;
stack<int> s;
for(int i=[Link]()-1;i>=0;i--){
while(![Link]() && [Link]()<=nums2[i]){
[Link]();
}
if([Link]()){
m[nums2[i]]=-1;
}
else{
m[nums2[i]]=[Link]();
}
[Link](nums2[i]);
}
// setup them into nums1 order wise
for(int i=0;i<[Link]();i++){
nums1[i]=m[nums1[i]];
}
return nums1;
}
};

Example Walkthrough
Let’s consider an array:
[6, 8, 0, 1, 3]
1. Start from the last element (3)
o Since it’s the last, its Next Greater Element = -1
o Push 3 onto the stack.
2. Move to 1
o The top of the stack is 3, which is greater than 1.
o So, Next Greater Element for 1 = 3.
o Push 1 onto the stack.

97 BBN
 3. Move to 0
o The top of the stack is 1, which is greater than 0.
o So, Next Greater Element for 0 = 1.
o Push 0 onto the stack.
4. Move to 8
o The stack contains [3, 1, 0], but all these values are smaller than 8.
o Pop all smaller values.
o Since the stack is empty now, Next Greater Element for 8 = -1.
o Push 8 onto the stack.
5. Move to 6
o The stack’s top is 8, which is greater than 6.
o So, Next Greater Element for 6 = 8.
o Push 6 onto the stack.
Final Output
For [6, 8, 0, 1, 3], the Next Greater Elements are:
[8, -1, 1, 3, -1]

Finding the Largest Rectangle in a Histogram

A histogram is a type of graph that consists of
different vertical bars. Each bar has a given height.
The task is to find the largest rectangular area that
can be formed within the histogram.

Understanding Rectangles in a
Histogram
Each rectangle in the histogram is formed by using one
or more bars. The area of any rectangle is calculated
using the formula:
Area=Height×Width
Our goal is to maximize this area.
Approach to Solve the Problem
There are two main approaches:
1. Brute Force Approach (Basic method)
2. Optimal Approach (Efficient method using stacks)

1. Brute Force Approach (Simple but Slow)

We check all possible rectangles in the histogram.

We calculate their areas and store the maximum area found.

Time complexity: O(N²) (Not efficient for large inputs).

Example:
1. Consider each bar one by one.
2. Expand left and right until the height condition is met.
3. Compute the area for each possible rectangle.
4. Keep track of the largest area.

98 BBN
2. Optimal Approach using Stack (Fast)
Instead of checking all possible rectangles, we use a stack to keep track of bars efficiently.
Steps for the Optimal Approach:
1. Use a stack to store the indices of histogram bars.
2. Process each bar:
o If the stack is empty or the current bar is taller than the top of the stack, push it.
o If a smaller bar is found, pop elements from the stack and compute areas using the
popped height.
3. Calculate width using the nearest smaller bars on the left and right.
4. Store the maximum area.
Time complexity: O(N) (Efficient).
finding the Nearest Smaller Element (Left Smaller)
The Nearest Smaller Element means finding the closest smaller value to the left of each
element in an array. This is also known as Previous Smaller Element.
Approach
1. Use a Forward Loop
o Since we need to check left-side elements, we traverse from left to right (i = 0 to
n).
2. Using a Stack
o We use a stack to efficiently find the left smaller element.
o For each element, check whether a smaller element exists in the stack.

Step-by-Step Process
1. Start iterating from left to right.
2. If the stack is empty, there is no smaller element → Answer is -1.
3. If the top of the stack is smaller than the current element, that is our answer.
4. If the top is greater, pop elements until we find a smaller value or the stack becomes
empty.
5. Push the current element’s index into the stack.
6. Repeat the process for all elements.

Example
Array: [2, 1, 5, 6, 2, 3]
Elemen Stack Left Stack
t (Before) Smaller (After)
2 Empty -1 [2]
1 [2] -1 (pop 2) [1]
5 [1] 1 [1, 5]
6 [1, 5] 5 [1, 5, 6]
2 [1, 5, 6] 1 (pop 6, 5) [1, 2]
3 [1, 2] 2 [1, 2, 3]

Implementation (C++)
class Solution {

99 BBN
public:
int largestRectangleArea(vector<int>& h) {
int n=[Link]();
stack<int> s;
vector<int> RSmall(n,n);
vector<int> LSmall(n,-1);

for(int i=n-1;i>=0;i--){
while(![Link]() && h[i]<=h[[Link]()]){
[Link]();
}
if(![Link]()){
RSmall[i]=[Link]();
}
[Link](i);
}

while(![Link]()){
[Link]();
}

for(int i=0;i<n;i++){
while(![Link]() && h[i]<=h[[Link]()]){
[Link]();
}
if(![Link]()){
LSmall[i]=[Link]();
}
[Link](i);
}

int maxArea=0;
for(int i=0;i<n;i++){
int width=RSmall[i]-LSmall[i]-1;
maxArea=max(maxArea,h[i]*width);
}
return maxArea;
}
};

Time Complexity
 Each element is pushed once and popped once from the stack.
 O(N) time complexity (efficient solution).

Trapping Rain Water Problem:

🔸 Problem Goal:

100 BBN
Find how much rainwater is trapped between the bars.

🔸 Space Optimized Two Pointer Approach:

Instead of storing leftMax[] and rightMax[] arrays, we use two pointers and two variables to
calculate on the go.

🔸 What we use:
 left pointer → starts from 0
 right pointer → starts from n - 1
 leftMax → maximum height from the left
 rightMax → maximum height from the right
 ans → to store total water

🔸 Logic:
1. Run a loop while left < right.
2. At each step, update leftMax and rightMax.
3. If leftMax < rightMax:
→ Water trapped = leftMax - height[left]
→ Add to ans
→ Move left++
4. Else:
→ Water trapped = rightMax - height[right]
→ Add to ans
→ Move right—
class Solution {
public:
int trap(vector<int>& h) {
int l=0,r=[Link]()-1;
int lmax=h[0],rmax=h[r];
int totalWater=0;
while(l<r){
lmax=max(lmax,h[l]);
rmax=max(rmax,h[r]);
if(lmax<rmax){
totalWater+=lmax-h[l];
l++;
}
else{
totalWater+=rmax-h[r];

101 BBN
 r--;
}

}
return totalWater;
}
};

🔸 Why this works:

 Water trapped depends on shorter boundary (left or right).
 We always move the pointer with smaller max value.
 This helps calculate trapped water without storing extra arrays.

🔸 Example:
For bars [4, 0, ..., 10]
 Left boundary = 4
 Right boundary = 10
 Water trapped over 0 = 4 - 0 = 4
 Even if there's a big bar like 12 on right → doesn’t matter
because left boundary (4) is still the limiting factor.

🔸 What is the Problem?

You are given a 2D array (a square matrix) where:
CopyEdit
arr[i][j] = 1 → person i knows person j
arr[i][j] = 0 → person i does NOT know person j
A celebrity is someone who:
 ✅ Is known by everyone
 ❌ But does not know anyone
We have to find the index of the celebrity, or return -1 if no celebrity exists.

🔸 Real Life Example:

Imagine you’re at a party with 3 people:
 Person 0
 Person 1

102 BBN
  Person 2
And you get this matrix:
arr = [
[0, 1, 0], # Person 0 knows person 1
[0, 0, 0], # Person 1 knows no one
[0, 1, 0] # Person 2 knows person 1
]
Now let's check:
 Person 0 knows person 1
 Person 1 knows no one ✅
 Person 2 knows person 1
So, everyone knows Person 1 and Person 1 knows no one → 🎉 Person 1 is the celebrity!

🔸 More Examples:
✅ Example 1:
arr = [
[0, 1, 1],
[0, 0, 1],
[0, 0, 0]
]
Check person 2:
 Person 0 knows 2 ✅
 Person 1 knows 2 ✅
 Person 2 knows no one ✅
So, person 2 is celebrity → ✅ Answer: 2

❌ Example 2:
arr = [
[0, 1, 0],
[0, 0, 1],
[1, 0, 0]
]
Check all:
 No one is known by all
 And no one fulfills the condition
So → ❌ No celebrity → Answer: -1

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

// Function to check if person a knows person b

bool knows(vector<vector<int>>& M, int a, int b) {
return M[a][b] == 1;
}

int findCelebrity(vector<vector<int>>& M, int n) {

103 BBN
 stack<int> s;

// Step 1: Push all persons in the stack

for (int i = 0; i < n; i++) {
[Link](i);
}

// Step 2: Get a candidate

while ([Link]() > 1) {
int a = [Link](); [Link]();
int b = [Link](); [Link]();

if (knows(M, a, b)) {
// a cannot be celebrity
[Link](b);
} else {
// b cannot be celebrity
[Link](a);
}
}

int candidate = [Link]();

// Step 3: Check if candidate is celebrity

for (int i = 0; i < n; i++) {
if (i != candidate) {
if (knows(M, candidate, i) || !knows(M, i, candidate)) {
return -1;
}
}
}

return candidate;
}

int main() {
vector<vector<int>> arr = {
{0, 1, 0},
{0, 0, 0},
{0, 1, 0}
};

int result = findCelebrity(arr, 3);

if (result == -1)
cout << "No celebrity found\n";
else
cout << "Celebrity is person: " << result << endl;

return 0;
}
class Solution {

104 BBN
public:
int trap(vector<int>& height) {

}
};

🧠 What is the Problem About?

We are asked to design an LRU (Least Recently Used) Cache.
LRU Cache is a special type of memory or temporary storage that stores data based on usage
priority.

💡 Key Concept: What is a Cache?

 Cache is a temporary storage that holds data for quick access.
 It has a limited capacity.
 It stores data in the form of key-value pairs.
 Most recently used data is given higher priority.
 Least recently used (old) data is removed to make space for new data.

✅ What is LRU (Least Recently Used)?

 It keeps recently used data in memory.
 If the cache is full and a new item needs to be added:
o It removes the least recently used item.
o Inserts the new item.
 If a value is accessed or added, it's treated as recently used.

Functions to Implement
You will implement a class called LRUCache with:
1. Constructor(capacity):
o Takes the max size of the cache.
2. get(key):
o Returns the value of the given key.
o If key is not found, return -1.
o Also updates usage priority.
3. put(key, value):
o Inserts or updates the key with the value.
o If cache is full, it removes the least recently used item before inserting.

📈 Example Explained (with capacity = 2)

1. put(1, 1) → cache: {1=1}
2. put(2, 2) → cache: {1=1, 2=2}
3. get(1) → returns 1, cache becomes: {2=2, 1=1}
4. put(3, 3) → removes 2, cache: {1=1, 3=3}
5. get(2) → returns -1 (not found)
6. put(4, 4) → removes 1, cache: {3=3, 4=4}
7. get(1) → returns -1
8. get(3) → returns 3, cache: {4=4, 3=3}
105 BBN
 9. get(4) → returns 4, cache: {3=3, 4=4}

⚙️How to Design It? (Data Structures)

We use:
1. Doubly Linked List – to maintain the order of usage:
o Head → Most recently used
o Tail → Least recently used
2. Hash Map (or unordered_map) – to store key to node reference for O(1) access.

📌 Why Doubly Linked List?

 It helps us:
o Insert a new node at the head (recent).
o Remove a node from the tail (oldest).
o Move any accessed node to the front.
 Each node stores:
o key
o value
o prev
o next

🔹 What is addNode() Function?

 We call addNode() when we want to insert a new node.
 It also handles the case when same key data is inserted again.
 First, it deletes old connection, then inserts the new data (like 13) and adds it into the map
and linked list.

🔹 Special Case: Same Key Reinsertion

 If same key already exists:
o Delete old node.
o Insert the new node using addNode().

🔹 Corner Case: When Cache is Full (Capacity Reached)

 Example:
o put(1,1) → inserted at start.
o put(2,2) → inserted at start, so list becomes: 2 (MRU) → 1 (LRU).
o get(1) → Now 1 becomes MRU, and 2 becomes LRU.
o put(3,3) → Cache is full, so remove LRU (2), then insert 3 at start.

🔹 How to remove Least Recently Used (LRU)?

 LRU is always the node before the tail.
 So we:
1. Remove key from the map.
2. Call deleteNode() on tail’s previous node.

106 BBN
🔹 Steps for put() Function:
1. If the key already exists:
o Delete the existing node.
o Remove from the map.
2. If cache is full (size == capacity):
o Remove LRU (tail's previous node).
o Delete from map.
3. Create a new node and insert it using addNode().
4. Add it to the map.

🔹 addNode(node) Function (Insert node after head)

 Make 4 connections:
o [Link] → newNode
o [Link] → head
o [Link] → oldNext
o [Link] → newNode

🔹 deleteNode(node) Function
 Reconnect:
o [Link] → [Link]
o [Link] → [Link]

🔹 Time Complexity:
 addNode() → Constant time (O(1))
 deleteNode() → Constant time (O(1))
 put() → Constant time (O(1))

🔹 get(key) Function:
 If key exists:
o Move that node to the most recently used (MRU) position using:
 deleteNode()
 addNode()
o Return value.
 If not, return -1.

✅ What is Queue?
 Queue is a First-In-First-Out (FIFO) data structure.
 This means the element which goes first, comes out first.
 Queue has two ends:
o Front: from where elements are removed.
o Rear: where new elements are added.

✅ Queue Main Operations

1. Push (Enqueue)

107 BBN
 o Adding element to the rear of queue.
o Example: If we push 1, then 2, then 3 → They are added at the rear (last).
2. Pop (Dequeue)
o Removing element from the front of queue.
o Example: If we pop now → 1 is removed first, then 2, then 3.
3. Front
o Checking the front element (the element to be removed next).
o In queue, front element is most important like:
 Top in Stack.
 Head in Linked List.

✅ FIFO vs LIFO
Stack = LIFO (Last In, First Out)
Queue = FIFO (First In, First Out)
Example:
 We push: 1, 2, 3 → Pop will remove: 1, then 2, then 3.

✅ Real Life Examples of Queue

 People standing in line.
 New person comes at the end, and the first person leaves first.

✅ Queue Implementation
We can implement queue in many ways, here we use Linked List.
Important Functions to Implement:
1. Front() – Return front element (linked list head's data).
2. Push() – Insert at rear (linked list's tail).
3. Pop() – Delete from front (delete linked list's head).
All work in O(1) time.

✅ Push/Pop Alternate Names

Push = enQueue (adding data)
Pop = deQueue (removing data)
⚠️Don’t confuse this deQueue with Deque (Double Ended Queue).

✅ How Linked List helps in Queue?

 Head of linked list = front of queue
 Tail of linked list = rear of queue
Example:
If queue = [1, 2, 3]
Then linked list = 1 → 2 → 3
 Push 4 = add at tail → 1 → 2 → 3 → 4
 Pop = remove head → 2 → 3 → 4

✅ Steps to Implement Queue with Linked List (in C++)

1. Create a Node class

108 BBN
 o Each node has data and next pointer.
2. Create Queue class
o It has two pointers: head and tail.
3. Constructor
o Initialize head and tail as NULL.
4. Push function
o Add new node at tail.
5. Pop function
o Remove node from head.
6. Front function
o Return data of head node.
#include <iostream>
using namespace std;

class Node
{
public:
int data;
Node *next;
Node(int d)
{
data = d;
next = nullptr;
}
};
class Queue
{

Node *head;
Node *tail;

public:
Queue()
{
head = tail = nullptr;
}
void push(int val)
{
Node *newNode = new Node(val);
if (empty())
{
head = tail = newNode;
return;
}
else
tail->next = newNode;
tail = newNode;
}
void pop()
{

109 BBN
 if (empty())
return;
if (head->next == nullptr)
{
head = tail = nullptr;
return;
}
Node *temp = head;
if (head->next == nullptr)
{
head = tail = nullptr;
delete temp;
return;
}
else
{
head = head->next;
delete temp;
return;
}
}
int front()
{
if (empty())
return -1;
return head->data;
}
bool empty()
{
return head == nullptr;
}
};

int main()
{
Queue q;
[Link](4);
[Link](8);
[Link](0);
[Link](-1);
while (![Link]())
{
cout << [Link]() << " ";
[Link]();
}
[Link]();
return 0;
}

110 BBN
Difference between Queue and Deque:
Feature Queue Deque (Double Ended Queue)

Meaning FIFO – First In First Out Insert and delete from both ends

Insertion Only at rear end Both front and rear ends

Deletion Only from front end Both front and rear ends

Flexibility Less flexible More flexible

Example Line of people at a counter Browser history (back and forward stack)

#include <iostream>
#include <queue>
#include <deque>
using namespace std;

int main()
{
queue<int> q;
[Link](1);
[Link](2);
[Link](3);
[Link](4);
while (![Link]())
{
cout << [Link]() << " ";
[Link]();
cout << endl;
}
deque<int> dq;
dq.push_back(1);
dq.push_back(2);
dq.push_front(3);
cout << [Link]() << " " << [Link]() << endl;

return 0;
}

🔄 What is a Circular Queue?

 A queue is a FIFO (First In, First Out) structure.

111 BBN
  In a normal queue, we insert (push) elements from the rear and remove (pop) them from the front.

🌀 Circular Queue

 It is like a normal queue but circular in shape.

 It also has a front and a rear pointer.
 Push (insert) happens at the rear, pop (remove) happens from the front.
 The difference is: Circular Queue has a fixed size and when we reach the end, we can go back to the
start if space is available.

🧠 Why Circular?

 In a normal queue, once the array is full, we can't use the empty space at the start.
 In Circular Queue, we reuse that empty space by wrapping around.

🛠 How to Implement Circular Queue?

 Use a fixed size array.

 Keep 3 things:
o front pointer
o rear pointer
o current size of the queue
 Initially, front = -1, rear = -1, size = 0

112 BBN
📌 Push Operation (Insert)

1. First check if the queue is full: size == capacity

2. If not full:
o Update rear = (rear + 1) % capacity
o Insert the element at queue[rear]
o If inserting first element, set front = 0
o Increase size

📌 Pop Operation (Remove)

1. First check if the queue is empty: size == 0

2. If not empty:
o Get the element from queue[front]
o Update front = (front + 1) % capacity
o Decrease size

💡 Example

If capacity is 3 and you insert:

 Push 1 → rear = 0
 Push 2 → rear = 1
 Push 3 → rear = 2

Now pop:

 Pop → front = 0 → remove 1 → front = 1

Now insert again:

 Push 4 → rear = (2 + 1) % 3 = 0 → element goes at index 0

This is how it wraps around!

#include <iostream>
using namespace std;

class CQueue
{
public:
int cap, currSize = 0;
int *arr;
CQueue(int val)

113 BBN
 {
cap = val;
arr = new int[cap];
}

int f = 0;
int r = -1;

int front()
{
if (isEmpty())
{
cout << "Queue is Empty" << endl;
return -1;
}
return arr[f];
}

void push(int val)

{
if (currSize == cap)
{
cout << "Queue is Full\n";
return;
}
r = (r + 1) % cap;
arr[r % cap] = val;
currSize++;
}
void pop()
{
if (isEmpty())
{
cout << "Queue is Empty" << endl;
return;
}
f = (f + 1) % cap;
currSize--;
}
bool isEmpty()
{
return currSize == 0;
}

~CQueue()
{
delete[] arr;
}

114 BBN
};
int main()
{
CQueue qq(3);
[Link](1);
[Link](3);
[Link](5);
[Link]();
[Link](2);
while (![Link]())
{
cout << [Link]() << " ";
[Link]();
}
}

💡 Problem Statement

We need to implement a Stack (LIFO - Last In First Out) using two Queues (FIFO - First In First Out).

📚 Stack Basic Functions to Implement

We need to implement these 4 basic functions of a stack:

1. push(x) – Add element x to the top.

2. pop() – Remove and return the top element.
3. top() – Return the top element.
4. empty() – Return true if stack is empty.

⚙️Strategy to Use Queues for Stack

Since a stack is LIFO and a queue is FIFO, we will:

 Use two queues: q1 (main queue) and q2 (helper queue).

 Store stack elements in q1 such that top of the stack is at front of q1.

✅ Push Operation (O(n))

To push an element, we need to:

115 BBN
 1. Move all elements from q1 to q2.
2. Push the new element into q1.
3. Move all elements back from q2 to q1.

📌 After this, q1 will have the latest pushed element at the front.

✅ Pop Operation (O(1))

 Simply pop the front element of q1, which represents the top of the stack.

✅ Top Operation (O(1))

 Just return the front of q1, as it holds the top of the stack.

✅ Empty Operation (O(1))

 Return [Link]() to check if the stack is empty.

💻 C++ Code
class MyStack {
public:
queue<int> q1, q2;

MyStack() {
// Constructor: no special initialization needed
}

void push(int x) {
// Step 1: Move all elements from q1 to q2
while (![Link]()) {
[Link]([Link]());
[Link]();
}

// Step 2: Push new element to q1

[Link](x);

// Step 3: Move all elements back to q1

while (![Link]()) {
[Link]([Link]());
[Link]();
}
}

int pop() {

116 BBN
 int val = [Link]();
[Link]();
return val;
}

int top() {
return [Link]();
}

bool empty() {
return [Link]();
}
};

🔍 Time Complexity

 push: O(n) because of moving elements

 pop, top, empty: O(1)

🔶 Problem Statement

Given a string of characters (like a stream), you have to find the first non-repeating (unique) character at
every point in time.

If no non-repeating character is available, return -1.

🔶 Example

Let the stream be: aabc

1. a → First non-repeating = a
2. aa → All are repeating → -1
3. aab → b is first non-repeating
4. aabc → b is still first non-repeating

Output: a -1 b b

🔶 Approach (C++ Style Thinking)

To solve this efficiently, we need two main things:

✅ 1. Frequency Map

To count how many times each character has appeared.

cpp

117 BBN
CopyEdit
unordered_map<char, int> freq;
✅ 2. Queue

To keep characters in the order they arrive. It will help us know which character came first.

cpp
CopyEdit
queue<char> q;

🔶 Logic

1. Loop through the string character by character.

2. For each character:
o Increase its frequency in the map.
o Push it into the queue.
3. While the queue is not empty:
o If the front character's frequency > 1 → It’s repeating → Remove it.
o Else → This is the first non-repeating → Print it.
4. If queue is empty → Print -1.

🔶 Dry Run Example

text
CopyEdit
Input: a a b c

Step-by-step:
1. 'a' → freq[a]=1 → push 'a' → front is 'a' → output 'a'
2. 'a' → freq[a]=2 → queue has 'a' → freq >1 → pop 'a' → queue empty → output '-1'
3. 'b' → freq[b]=1 → push 'b' → front is 'b' → output 'b'
4. 'c' → freq[c]=1 → queue is [b,c] → front 'b' is non-repeating → output 'b'

🔶 Final Output:
a -1 b b

🔶 C++ Code
cpp
CopyEdit
#include <iostream>
#include <unordered_map>
#include <queue>
using namespace std;

string firstNonRepeating(string s) {

118 BBN
 unordered_map<char, int> freq;
queue<char> q;
string result = "";

for (char ch : s) {
freq[ch]++;
[Link](ch);

while (![Link]() && freq[[Link]()] > 1) {

[Link]();
}

if (![Link]()) {
result += [Link]();
} else {
result += '#'; // Or use "-1" if you want
}
}
return result;
}

🔶 Time and Space Complexity

 Time: O(N)
 Space: O(1) → Since only 26 lowercase letters exist

🧠 Problem Name: Sliding Window Maximum (Leetcode Q.239)

🔶 What is Given?

 An array of numbers
 A value k (the size of the sliding window)

🟡 What We Have to Do?

We need to find the maximum number in every window of size k as we slide the window from left to right.

📌 Example:

If the array is: [1, 3, -1, -3, 5, 3, 6, 7]

And k = 3, it means:

 First window: [1, 3, -1] → Max = 3

 Second window: [3, -1, -3] → Max = 3
 Third window: [-1, -3, 5] → Max = 5
 Fourth window: [-3, 5, 3] → Max = 5
 Fifth window: [5, 3, 6] → Max = 6
 Sixth window: [3, 6, 7] → Max = 7

✅ Final answer: [3, 3, 5, 5, 6, 7]

119 BBN
🧾 Step-by-Step Solutions:

🔹 1. Naive Approach (Brute Force)

 Use two loops:

o Outer loop: to select starting point of the window
o Inner loop: to find the max in every window of size k
 Time Complexity: O(n * k)

✅ Simple Idea:
cpp
CopyEdit
for i = 0 to n-k:
max = find maximum in window [i to i+k-1]
store max in answer

🔹 2. Optimal Approach (Using Deque - Double Ended Queue)

 Use a deque to store useful elements only

 Only keep elements in the deque which are candidates for the max of current and future windows

🔑 Rules to Use Deque:

1. Remove elements from front of deque if they are out of the current window
2. Remove smaller elements from the back of deque because they can never be max if a bigger value
comes after them
3. Add the current element at the back

✅ Time Complexity: O(n)

🧠 Main Logic Summary:

1. At the end of the loop, we push the last element (7) inside the deque dq.
2. After that, the loop is finished, meaning we start analyzing the next window.
3. The maximum element of the last window will always be at the front of the deque, which in our
example is 7.
4. So, after the full loop completes, we add the front of dq to our result list.

🔍 Important Detail in Loop:

 We need to remove elements from dq that do not belong to the current window.
 For this, instead of storing the actual elements, we will now store their indices in the deque.

📌 Why store indices instead of values?

120 BBN
  If we know an index, we can track the position of that element and decide if it's inside the current
window or not.

✅ Example:

Suppose our array is like this:

[1, 3, -1, -3, 5, 3, 6, 7]

Let’s say we are processing a window of size k = 3.

 First we store index 0 (value = 1)

 Then we process index 1 (value = 3), remove smaller elements from the back, and store index 1
 We keep doing this, but store indices, not values.

This helps us later to check:

Is the element at the front of dq still inside the current window?

🧾 How to check if an index is outside the window:

Use this condition:

if ([Link]() <= i - k)
dq.pop_front();

 i = current index
 k = size of window
 If the index at the front of the deque is less than or equal to (i - k), it means that element has gone out
of the window, so we remove it.

🎯 For example:

If i = 4 and k = 3, then:

 Start of the current window = i - k + 1 = 2

 So, any index less than 2 is not part of this window and should be removed.

class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> dq;
vector<int> res;
//step 1
for(int i=0;i<k;i++){

121 BBN
 while([Link]()>0 && nums[[Link]()]<=nums[i]){
dq.pop_back();
}
dq.push_back(i);
}

//step 2
for(int i=k;i<[Link]();i++){
res.push_back(nums[[Link]()]);
while([Link]()>0 && [Link]()<=i-k){
dq.pop_front();
}
while([Link]()>0 && nums[[Link]()]<=nums[i]){
dq.pop_back();
}
dq.push_back(i);
}
res.push_back(nums[[Link]()]);
return res;
}
};

🚉 Problem Overview: Circular Gas Station Problem

 We are given two arrays:

1. gas[i]: the amount of fuel we get at station i.
2. cost[i]: the fuel needed to go from station i to station i+1.
 The stations form a circular path, so after the last station, we go back to the first.

🎯 Goal

We have to find the starting station index from where we can complete the full circular tour.
If it's not possible to complete the tour from any station, we return -1.

🔍 Understanding Through Example

Let’s say:
gas = [1, 2, 4]
cost = [3, 4, 1]

Try from index 0:

 Fuel at 0 = 1, cost to next = 3 → Not enough

Try from index 1:

122 BBN
  Fuel = 2, cost = 4 → Not enough
Try from index 2:
 Fuel = 4, cost = 1 → ✅ Possible
o Remaining = 3 → Add gas at next station... continue...

This means station 2 is a valid starting point.

❌ When is Solution Not Possible?

Let’s say:
gas = [2, 3, 4]
cost = [3, 4, 3]

Total gas = 2+3+4 = 9

Total cost = 3+4+3 = 10

▶️Since total gas < total cost, it’s impossible to complete the tour.
🔁 So, return -1.

✅ Main Condition for Valid Tour

To ensure a solution is possible:

Total Gas ≥ Total Cost

This is the first check you must always do!

🚀 How to Find the Start Index

Once Total Gas ≥ Total Cost, a valid solution will always exist.
But we need to find the unique starting index where the tour is possible.

Use this approach:

text
CopyEdit
1. Start from index 0
2. Keep a variable `fuel = 0`
3. Traverse all stations:
a. Add `gas[i] - cost[i]` to `fuel`
b. If `fuel` < 0 → we cannot start from previous start, so update `start = i + 1` and
reset `fuel = 0`
4. At the end, return the final `start` index

🧠 Why This Works?

123 BBN
  If at any point your fuel goes below 0, it means the tour can’t start from that or any previous station.
 So, we shift the starting point forward.

🧪 Final Example for Practice

Let:
gas = [5, 1, 2, 3, 4]
cost = [4, 4, 1, 5, 1]
Total gas = 15, total cost = 15 ✅ So solution exists.

Use the above algorithm and find the correct starting index (It will be 4).

class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int totgas=0,totcost=0;
int start=0,currCost=0;
for(int i=0;i<[Link]();i++){
totgas+=gas[i];
totcost+=cost[i];
currCost+=gas[i]-cost[i];
if(currCost<0){
start=i+1;
currCost=0;
}
}
return totgas < totcost ? -1 : start;
}
};

What is a Hierarchical Data Structure?

Until now, we studied Linear Data Structures like Arrays, Vectors, and Linked Lists, which store data in a
straight line.

But a Binary Tree stores data in levels, in a hierarchical way.

Real-life Examples:

1. Folders in a computer: There are main folders, subfolders, and files inside them.
2. Family Tree: Grandparents → Parents → You.

We use Tree Data Structures to store this kind of data. In computer science, when we have to store data in
multiple levels, we use Trees.

What is a Tree in DSA?

124 BBN
A Tree is made of Nodes.
Each node stores data, just like in a Linked List.
The top node in a tree is called the Root Node.

From the root, there are branches that connect to other nodes. This continues down in levels.

In DSA, we draw trees starting from the root at the top, not like real trees where the root is at the bottom.

Important Terms

 Node: A unit in a tree that stores data.

 Root: The top node of the tree.
 Branch: Connects one node to another.
 Parent: A node that has children.
 Child: A node that comes from a parent node.

Example:
If node 1 connects to nodes 2, 3, and 4, then:

 1 is the parent
 2, 3, and 4 are its children.

What is a Binary Tree?

A Binary Tree is a special kind of tree where each node can have at most 2 children.
These children are usually called:

 Left Child
 Right Child

If a node has more than two children, it is not a binary tree.

To convert a normal tree into a binary tree:

 Make sure every node has at most two children.

Example:

 Node 1 has children 2 and 3 → valid.

 Node 2 has children 5 and 6 → valid.
 Node 3 has only one child → also valid.

This tree is now a Binary Tree.

🌲 Preorder Sequence Concept:

125 BBN
Preorder = Root -> Left Subtree -> Right Subtree
So if we go in order:

 First element is the root.

 Then all elements of the left subtree.
 Then elements of the right subtree.

⚙️Step-by-Step Plan to Build the Tree:

1. We use a global/static variable called index, starting from -1.

It will keep track of which value we are using from the preorder array.
2. Each time we make a recursive call, we:
o Increase the index (i.e., index++)
o Create a new node with preorder[index]
3. Important:
If the value at preorder[index] is -1, it means this node is NULL.
So we don’t create a node and just return NULL.

🧱 Recursive Function buildTree():

This function:

 Takes the preorder array.

 Uses the global index.
 Creates a node with the current value.
 Then recursively builds the left child and right child.

🪜 Recursive Flow (Dry Run Example):

Let’s say:
preorder = [1, 2, -1, -1, 3, -1, -1]

Step Value Action

1 1 Create root node (1)
2 2 Left child of 1 → node (2)
3 -1 Left child of 2 → NULL
4 -1 Right child of 2 → NULL
5 3 Right child of 1 → node (3)
6 -1 Left child of 3 → NULL
7 -1 Right child of 3 → NULL

➡️Final Tree:

126 BBN
 1
/ \
2 3

🔁 Summary of Rules:

 Use static/global index = -1.

 In each call: index++
 If value is -1 → return NULL
 Else → create node
o node->left = buildTree(preorder)
o node->right = buildTree(preorder)

🌳 What is Preorder Traversal in a Tree?

In preorder traversal, we visit nodes in this order:

1. Visit the root node (print its value)

2. Traverse the left subtree
3. Traverse the right subtree

🔁 Step-by-step Understanding with Example Tree

Let's say the tree looks like:

markdown
CopyEdit
1
/ \
2 3
/ \
4 5
💡 How we traverse:

1. Start from 1 (this is the root) → print 1

2. Go to left child of 1 → it's 2 → print 2
o 2 has no children (both left and right are null)
o So, return back to 1
3. Now go to right child of 1 → it's 3 → print 3
o Go to left of 3 → 4 → print 4
o 4 has no children → return
o Go to right of 3 → 5 → print 5
o 5 has no children → return

✅ Final Output:
CopyEdit
1 2 3 4 5

🔧 How Preorder Code Works (in C++)

127 BBN
cpp
CopyEdit
void preorder(Node* root) {
if (root == NULL) return; // base case

cout << root->data << " "; // print root first

preorder(root->left); // then go left
preorder(root->right); // then go right
}

🧠 Key Points to Remember

 If the node is NULL, we just return → this is our base case.

 We always print the root first, then left subtree, then right subtree.
 Recursion helps us go deep into each side of the tree automatically.

Time Complexity

 We visit each node once, so time complexity is O(n), where n = number of nodes.

🔄 What is Inorder Traversal? (Short Intro)

In inorder, the steps are:

1. Traverse the left subtree

2. Print the root
3. Traverse the right subtree

So output of inorder for the same tree above will be: 2 1 4 3 5

🌳 Level Order Traversal (with new line for each level) – Easy English Notes

🔁 Basic Traversal Steps:

1. Start with the root node of the tree.

2. Create a queue (q) to store tree nodes.
3. Push the root node in the queue.
4. Then push a NULL marker to indicate end of level.

🔄 While the queue is not empty:

 Pop the front node of the queue.

 If the popped node is not NULL:
o Print its value.
o If it has a left child, push it to the queue.
o If it has a right child, push it to the queue.

128 BBN
  If the popped node is NULL:
o It means one level is completed.
o Print a new line.
o Check if the queue still has nodes left:
 If yes, push another NULL to mark the next level.

🔍 Why do we use NULL?

 NULL helps us mark the end of a level.

 When we pop NULL and the queue is not empty, that means next level has started, so we print a new
line.

💡 Key Points:

 Every node is inserted and removed only once from the queue.
 So the Time Complexity is O(n), where n = number of nodes.

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

class Node
{
public:
int data;
Node *left;
Node *right;
Node(int val)
{
data = val;
left = right = nullptr;
}
};
static int idx = -1;
Node *buildTree(vector<int> Order)
{
idx++;
if (Order[idx] == -1)
return nullptr;
Node *root = new Node(Order[idx]);
root->left = buildTree(Order);
root->right = buildTree(Order);
return root;
}
void preOrder(Node *root)
{

129 BBN
 if (root == nullptr)
return;
cout << root->data << " ";
preOrder(root->left);
preOrder(root->right);
}
void inOrder(Node *root)
{
if (root == nullptr)
return;

inOrder(root->left);
cout << root->data << " ";
inOrder(root->right);
}

void postOrder(Node *root)

{
if (root == nullptr)
return;

postOrder(root->left);
postOrder(root->right);
cout << root->data << " ";
}

void levelOrder(Node *root)

{
queue<Node *> q;
[Link](root);
[Link](nullptr);
while (![Link]())
{
Node *temp = [Link]();
[Link]();
if (temp == nullptr)
{
if (![Link]())
{
cout << endl;
[Link](NULL);
continue;
}
else
{
break;
}
}

130 BBN
 cout << temp->data << " ";
if (temp->left != nullptr)
{
[Link](temp->left);
}
if (temp->right != nullptr)
{
[Link](temp->right);
}
}
}

int main()
{
vector<int> Order = {1, 2, -1, -1, 3, 4, -1, -1, 5, -1, -1};
Node *root = buildTree(Order);
levelOrder(root);
return 0;
}

✅ Question: Find the Height of a Binary Tree

🧠 What is given?
You are given a Binary Tree.
You also have access to its root node.
You need to complete a function named height() that returns the height of the binary tree.

📏 Understanding Tree Height

 Height = Maximum depth of the tree

 For example, if a tree has 3 levels, then its height = 3

🔍 Another way to define height:

Maximum distance from the root node to any leaf node

A leaf node is a node with no left or right children.

💡 Example:
If a path from root to a leaf node has 3 nodes → then height = 3.

💻 Approach: Use Recursion

We can solve this problem using recursion.

👉 In recursion:

131 BBN
  Calculate the height of the left subtree
 Calculate the height of the right subtree
 Take the maximum of both, and add 1 (for the current root node)

📌 Formula:

height(root) = 1 + max(height(root->left), height(root->right))

🧪 Example Dry Run

 Suppose root is 1
 Left subtree height = 1
 Right subtree height = 2
 So, overall height = 1 + max(1, 2) = 3

⚠️Edge Case: Empty Tree

If the tree is empty (i.e., root is null),

Then the height should be 0.

📌 Base case in code:

if root is None:
return 0

💡 Goal:

We want to count the total number of nodes in a binary tree.

For example, if a tree has nodes: 1, 2, 3, 4, 5 → the total count should be 5.

🧠 Logic:

We will use recursion.

For any root node:

 Count all nodes in the left subtree

 Count all nodes in the right subtree
 Add 1 for the root node itself

👉 Formula:
Total Count = Left Count + Right Count + 1

132 BBN
🔁 How it works:

Suppose:

 Left subtree has 1 node

 Right subtree has 3 nodes
 Then total = 1 + 3 + 1 (root) = 5 nodes

🔧 Steps (Function):
cpp
CopyEdit
int count(TreeNode* root) {
if (root == NULL) return 0; // base case
int left = count(root->left); // count left subtree
int right = count(root->right); // count right subtree
return left + right + 1; // add root node
}

🧱 Base Case:

 If the tree is empty (root == NULL), return 0

 If only one node, return 1

🔄 Dry Run Example:

Let's say we have this tree:

markdown
CopyEdit
1
/ \
2 3
/ \
4 5

Step-by-step:

1. Start at root (1), go to left → 2

o 2 has no children → return 1
2. Go to right → 3
o 3 calls 4 → returns 1
o 3 calls 5 → returns 1
o Total for 3 = 1 + 1 + 1 = 3
3. Back to root (1): left = 1, right = 3

133 BBN
 o Total = 1 + 3 + 1 = 5

🧮 Time Complexity:

 We visit every node once →

Time = O(n) where n is the number of nodes

What is Maximum Width of a Binary Tree?

 Maximum width means:

The longest distance (in terms of number of nodes) between the leftmost and rightmost nodes at any
level of the tree.
 Even if some nodes are missing, we imagine the tree as a Complete Binary Tree (CBT) to calculate
the width.

📘 What is a Complete Binary Tree (CBT)?

 In a CBT:
o All levels are completely filled except the last level.
o The last level is filled from left to right.

We imagine missing nodes in a CBT while calculating the width. This helps us count the "gap" caused by
missing nodes too.

📘 How to Calculate Maximum Width (Simple Idea)

1. Traverse the tree level-wise (use BFS with a queue).

2. For each level:
o Keep track of the first node's index (leftmost).
o Keep track of the last node's index (rightmost).
o Calculate width using formula:
width = end_index - start_index + 1
3. Keep updating the maximum width while traversing.

📘 What is CBT Indexing?

 If we represent a CBT in an array, we follow these rules:

o For a node at index i:
 Left child → 2*i + 1
 Right child → 2*i + 2
 Even if a node is missing, we keep a placeholder in the index (just like CBT).

134 BBN
📘 Example Breakdown

Let’s assume a tree:

markdown
CopyEdit
1
/ \
3 2
/ \
5 9

👉 Imagine it as CBT:

arduino
CopyEdit
Level 0: 1 → width = 1
Level 1: 3 2 → width = 2
Level 2: 5 _ _ 9 → width = 4 (includes missing nodes)

So, Maximum Width = 4

📘 Another Example

Assume a tree with 4 levels, and after imagining missing nodes using CBT:

 Level 1 → width = 1
 Level 2 → width = 2
 Level 3 → width = 4
 Level 4 → width = 7 (after including imaginary nodes)

👉 So, final answer = 7

📘 Final Logic for Coding

 Use BFS to traverse the tree level by level.

 Track each node’s CBT index using the formula.
 For each level:
o Calculate width using: end_index - start_index + 1
o Store max width.

class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
queue<pair<TreeNode*,unsigned long long >> q;
int maxWidth=0;

135 BBN
 [Link]({root,0});
while([Link]()>0){
int levsize=[Link]();
unsigned long long stridx=[Link]().second;
unsigned long long endidx=[Link]().second;
maxWidth=max(maxWidth,(int)(endidx-stridx+1));
for(int i=0;i<levsize;i++){
auto node=[Link]();
[Link]();
if([Link]->left){
[Link]({[Link]->left,2*[Link]+1});
}
if([Link]->right){
[Link]({[Link]->right,2*[Link]+2});
}

}
return maxWidth;
}
};

Introduction: Morris In-order Traversal

In in-order traversal, we visit nodes in this order: left subtree → root → right subtree.

For example, for a tree with the nodes 2, 1, 4, 3, 5, the in-order traversal sequence will be 2, 1, 4, 3, 5.

We know that recursion is an easy way to do in-order traversal. However, today we will learn a non-recursive
approach that doesn’t use a stack. Instead, we will create temporary threads in the tree to help with the
traversal.

Key Concept: In-order Predecessor

Before diving into the Morris In-order Traversal, we must understand the in-order predecessor of a node. This
is the node that comes before the current node in the in-order sequence.

For example:

 The in-order predecessor of node 3 is node 4 (because 4 comes before 3 in the in-order sequence).
 The in-order predecessor of node 1 is node 2 (because 2 comes before 1).

How Morris In-order Traversal Works

136 BBN
In a typical recursive approach, we can easily backtrack to the root after visiting the left or right subtrees.
However, in the iterative method, once we go to the left subtree, we don't have a direct way to come back to the
root.

Morris In-order Traversal solves this problem by creating temporary connections between nodes:

 When we move to the left subtree, we create a temporary link from the in-order predecessor to the
current node.
 After finishing the left subtree, we use this connection to return to the root.

In-order Predecessor in Morris Traversal

In Morris In-order Traversal, the in-order predecessor is the rightmost node in the left subtree of a node.

For example:

 For node 1, the in-order predecessor is node 4 (the rightmost node in the left subtree of node 1).

Step-by-Step Process of Morris In-order Traversal

1. Start at the root node.

2. If the current node has no left child, print the node’s value and move to the right child.
3. If the current node has a left child, find the in-order predecessor (the rightmost node in the left
subtree).
4. Create a temporary thread (link) between the in-order predecessor and the current node.
5. Move to the left child of the current node and repeat the process.
6. If a temporary thread exists, it means we’ve already visited the left subtree. We then:
o Remove the temporary thread,
o Print the current node’s value,
o Move to the right child of the current node.

Example Walkthrough

Let’s consider the following tree:

markdown
CopyEdit
1
/ \
2 3
/ \
4 5

 Start at node 1.

137 BBN
  Move to node 2 (left child). Since node 2 has a left child (node 4), we find the in-order predecessor of
node 2, which is node 4.
 Create a temporary thread from node 4 to node 2, then move to node 4.
 Since node 4 has no left child, print 4 and move back to node 2 using the temporary thread.
 Print node 2 and move to its right child, node 5.
 Repeat the same process until we finish traversing the entire tree.

class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
TreeNode* curr=root;
while(curr!=nullptr){
if(curr->left==nullptr){
ans.push_back(curr->val);
curr=curr->right;
}
else{
//Find Inorder Predecessor (IP)
TreeNode* IP =curr->left;
while(IP->right!=nullptr && IP->right!=curr){
IP=IP->right;
}
//Create IP
if(IP->right==NULL){
IP->right=curr;
curr=curr->left;
}
//Delete IP
else{
IP->right=nullptr;
ans.push_back(curr->val);
curr=curr->right;
}
}
}
return ans;
}
};

Time Complexity

 Morris In-order Traversal runs in O(n) time, where n is the number of nodes in the tree.
 This time complexity is the same as the recursive approach, but Morris traversal doesn’t require a stack
or recursion.

138 BBN
139 BBN