Arrays

Question 1: Largest Element

Example 1:Input: arr[] = {2, 5, 1, 3, 0} Output: 5

Explanation: 5 is the largest element in the array.

Approach 1: (basic approach)

 Sort the array in ascending order.
 Print the element at the (size of the array - 1)th index, which corresponds to the largest
element in the array.
Approach 2: (basic approach)
1. Start → Assume the first element is the maximum
2. Loop → Go through the remaining elements one by one
3. Compare → Is current element > max?
o Yes → Update max with current element
o No → Skip, move to next
4. End of loop → max holds the largest value

Question 2: Second Largest Element & Second Smallest

Element
Example 1:Input: [1, 2, 4, 7, 7, 5] Output: Second Smallest : 2 Second Largest : 5
Explanation: The elements are sorted as 1, 2, 4, 5, 7, 7.
Hence, the second smallest element is 2, and the second largest element is 5.

Example 2: Input: [1] Output: Second Smallest : -1 Second Largest : -1

Explanation: Since there is only one element in the array, it is both the largest and smallest
element.
Therefore, there is no second smallest or second largest element present.

Brute: Sort the array and give The element at the second index (index 1) is the second smallest
element. The element at the second index from the end (index length-2) is the second largest
element. Time Complexity: O(N log N), for sorting the array.
Space Complexity: O(1), as we are using a constant amount of space for variables.

Better: Perform a single traversal to find the smallest and largest elements in the array.
After that, traverse the array again to find the element just greater than the smallest element
(this will be the second smallest).
Similarly, find the element just smaller than the largest element (this will be the second largest).

// Edge case: when the array has less than 2 elements

if (n == 0 || n == 1)
cout << -1 << " " << -1 << endl; // If only one element, print -1 for both second
smallest and second largest

int small = INT_MAX, second_small = INT_MAX;

int large = INT_MIN, second_large = INT_MIN;
int i;

for (i = 0; i < n; i++) {

small = min(small, arr[i]); // Update the smallest element
large = max(large, arr[i]); // Update the largest element
}

for (i = 0; i < n; i++) {

if (arr[i] < second_small && arr[i] != small)
second_small = arr[i];
if (arr[i] > second_large && arr[i] != large)
second_large = arr[i];
}

Optimal: “Iski topi uske sar”…

To find the second smallest and second largest in one pass, we use four variables: small,
second_small, large, second_large. Initialize small and second_small to INT_MAX, and large and
second_large to INT_MIN so any array element can replace them.
For each element in the loop — if current < small, shift small into second_small and update
small. Else if current < second_small, just update second_small. Mirror logic for largest — if
current > large, shift large into second_large and update large. Else if current > second_large,
just update second_large.
After the loop, second_small and second_large hold the answers. Use else if so the same
element doesn't update both variables at once. Time complexity — O(n), single pass.
int secondSmallest(int arr[], int n) {
 if (n < 2)
return -1;
int small = INT_MAX;
int second_small = INT_MAX;

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

if (arr[i] < small) {
second_small = small;
small = arr[i];
}
else if (arr[i] < second_small && arr[i] != small) {
second_small = arr[i];
}
}
return second_small; // Return the second smallest element
}

int secondLargest(int arr[], int n) {

// Edge case: if the array has fewer than 2 elements
if (n < 2)
return -1;

int large = INT_MIN, second_large = INT_MIN;

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

// Update the largest and second largest values
if (arr[i] > large) {
second_large = large;
large = arr[i];
}
else if (arr[i] > second_large && arr[i] != large) {
second_large = arr[i];
}
}
return second_large; // Return the second largest element
}

Question 3: Check if an Array is Sorted

Example 1: Input: N = 5, array[] = {1,2,3,4,5} Output: True. Explanation: The given array is sorted
i.e Every element in the array is smaller than or equals to its next values, So the answer is True.
 bool isSorted(int arr[], int n) {
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// If any element is smaller than the previous one, return false
if (arr[j] < arr[i])
return false;
}
}

return true; // Return true if no unsorted elements are found

}

Optimal Approach
bool isSorted(int arr[], int n) {
for (int i = 1; i < n; i++) {
if (arr[i] < arr[i - 1]) // If any element is smaller than the previous one, return false
return false;
}

return true; // Return true if the array is sorted

}

Question 4: Remove Duplicates in-place from Sorted Array

Input: arr[]=[1,1,2,2,2,3,3] Output: [1,2,3,_,_,_,_]
Explanation: Total number of unique elements are 3, i.e[1,2,3] and Therefore return 3 after
assigning [1,2,3] in the beginning of the array.

Since we need to store only unique elements, we can use the set data structure. We can insert
all the elements of the array in the set irrespective of their frequency as set only allows one
occurence of each element.

unordered_set<int> seen;
int index = 0;

for (int num : nums) {

// If num is not in seen, it's unique
if ([Link](num) == [Link]()) {
// Add this num to the set of seen numbers
 [Link](num);
// Overwrite nums[index] with this unique num
nums[index] = num;

// Move index forward

index++;
}
}
// Return count of unique elements
return index;

Optimal Approch: Maintain index to store previous element and iteration starts from nums[1].
if the previous element is not equal to i th element then first increase the pointer then assign
the element. Return i+1; as the no. of unique element.

int removeDuplicates(vector<int>& nums) {

// If array is empty, return 0 directly
if ([Link]()) return 0;

// Pointer for the position of last unique element

int i = 0;

// Traverse the array starting from the second element

for (int j = 1; j < [Link](); j++) {
// If current element is different from last unique element
if (nums[j] != nums[i]) {
// Move pointer for unique element forward
i++;
// Place the new unique element at the next position
nums[i] = nums[j];
}
}

// i is index of last unique element, count = i + 1

return i + 1;
}
};

Question 5: Left Rotate the Array by One [very very Easy]

Example 1:Input: nums = [1, 2, 3, 4, 5] Output: [2, 3, 4, 5, 1]
Explanation: Initially, nums = [1, 2, 3, 4, 5] Rotating once to the left results in nums = [2, 3, 4, 5,
1].

void solve(int arr[], int n) {

int temp[n]; // Create a temporary array to store the shifted elements

// Shift the elements to the left by one position

for (int i = 1; i < n; i++) {
temp[i - 1] = arr[i];
}
temp[n - 1] = arr[0]; // The first element moves to the last position

// Print the rotated array

for (int i = 0; i < n; i++) {
cout << temp[i] << " "; // Print each element of the rotated array
}
cout << endl;
Optimal Approch:

void rotateArrayByOne(vector<int>& nums) {

// Store the first element in a temporary variable
int temp = nums[0];

// Shift elements to the left

for (int i = 1; i < [Link](); ++i) {
nums[i - 1] = nums[i];
}

// Place the first element at the end

nums[[Link]() - 1] = temp;
}

Question 5: Left Rotate the Array by k

What if you have been asked: Given an integer array nums, rotate the array to the right
by k steps, where k is non-negative.

- First you will make the temp array and starting from k to size of arr (n), fill or
reconstruct existing arr
ex: [1,2,3,4,5,6,7] and K = 3. Now k is pointing to ‘4’
- You created = [ 4,5,6,7]
 - Now in second loop you will start from Size – k (always pointing to new position)
and maintain index i = 0 which pointing to your new arr
- Now loop starts from n – k to n whatever the size remaining. Assign the first
element to that position.

for(int i = n – k; i < n; i++){

nums[i] = temp[index];
index++
}

Most optimal and easy method you can follow for reversing
k = k % [Link](); <-----we used this to avoid large number
Simple analogy → Clock has 12 hours. If someone says "rotate 14 hours" → 14 % 12 = 2 → just
move 2 hours forward, same result. 🕐

 Analogy with Large Array

Array → [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] → size = 10

k = 23

Without % → you'd rotate 23 times 😵

With % → 23 % 10 = 3 → only rotate 3 times ✅

void rotate(vector<int>& nums, int k) {

k = k % [Link]();
reverse([Link](), [Link]());
reverse([Link](), [Link]() + k);
reverse([Link]() + k, [Link]());
}

Question 6: Move all Zeros to the end of the array

Input: 1 ,0 ,2 ,3 ,0 ,4 ,0 ,1 . Output: 1 ,2 ,3 ,4 ,1 ,0 ,0 ,0 Explanation: All the zeros are moved to
the end and non-negative integers are moved to front by maintaining order

The extremely naive solution, we can think of, involves the use of an extra array. The algorithm
is as follows.

vector<int> temp([Link](), 0);

int index = 0;
// Traverse input array
for (int i = 0; i < [Link](); i++) {
 // If non-zero, add to temp
if (arr[i] != 0) {
temp[index] = arr[i];
index++;
}

Okay, that’s Good but you are using extra space, increase you thinking level now …
Think of two pointer approach

First find the index which is not 0, and assign it to index = i. now always start from index + 1
because you will get non zero element after index. Before that check if index is still -1 . if yes
then return. If not then iterate the array and find element which is not zero if found then swap
it with the index th element (0) and then increment index.

int index = -1;

for(int i = 0; i < [Link](); i++){
if(arr[i] == 0){
index = i;
break;
}
}

if(index == -1){
return;
}

for(int j = index + 1; j < [Link](); j++){

if(arr[j] != 0){
swap(arr[index] , arr[j]);
index++;
}
}

Question 7: Find the Missing Number

Input: arr[] = [8, 2, 4, 5, 3, 7, 1]
Output: 6
Explanation: All the numbers from 1 to 8 are present except 6.

now you have multiple approaches.

1. You will make two loops to run 1st loop runs till 1 to n (exactly) and second loop from 0 to n
-1

int n = [Link]() + 1; // given if vector has 4 element , 5th element is our ans
for(int i = 1; i <= n; i++){
bool found = false;
for(int j = 0; j < n - 1; j++){ //you would run 1 less because it is missing
if(arr[j] == i){
found = true;
break;
}
}
if(!found) return i;
}
return -1;

2nd method is Map method

take a map input all the element from 0 to N , then again iterate the array from 1 to N and if the
count to any element is 0 then that is your number and break.

unordered_map<int,int>mpp;

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

mpp[arr[i]]++;
}

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

if(mpp[i] == 0){
return i;
break;
}
}

return [Link]() + 1; // for the case input = 1 then missing is obvious next number.

Most optimal method : sum all the integers

int n = [Link]() + 1;

// Calculate the sum of array elements

int sum = 0;
for (int i = 0; i < n - 1; i++) {
sum += arr[i];
 }

// Calculate the expected sum

long long expSum = (n *1LL* (n + 1)) / 2;

// Return the missing number

return expSum - sum;

Question 7: Count Maximum Consecutive One's in the array

Simply count the count the no. of 1’s if you stuck save the 1’s (maximum) and reset the counter.
Input: nums = [1,1,0,1,1,1]

Output: 3

Explanation: The first two digits or the last three digits are consecutive 1s. The maximum
number of consecutive 1s is 3.

int findMaxConsecutiveOnes(vector<int> &nums) {

// Variable to store current count of consecutive 1's
int cnt = 0;
// Variable to store maximum consecutive 1's
int maxi = 0;

// Traverse the array

for (int i = 0; i < [Link](); i++) {
// If current element is 1, increment count
if (nums[i] == 1) {
cnt++;
} else {
// If element is 0, reset count
cnt = 0;
}

// Update maximum if current count is greater

maxi = max(maxi, cnt);
}

// Return maximum consecutive 1's

return maxi;
}
Question 8: Find the number that appears once, and the other
numbers twice (simplest)
Example 1:

Input Format: arr[] = {2,2,1}

Result: 1

Explanation: In this array, only the element 1 appear once and so it is the answer.

Approach
Do xor of all the present element

int ans = 0;
for(int i = 0; i < [Link](); i++){
ans ^=nums[i];
}
return ans;

Question 9: Longest Subarray with given Sum K(Positives)

Example 1:Input: nums = [10, 5, 2, 7, 1, 9], k = 15

Output: 4

Explanation: The longest sub-array with a sum equal to 15 is [5, 2, 7, 1], which has a length of 4.
This sub-array starts at index 1 and ends at index 4, and the sum of its elements (5 + 2 + 7 + 1)
equals 15. Therefore, the length of this sub-array is 4.

Approach 1: Brute force

It is easy approach you will run 3 loops

i. From 0 to N where i = 0 ---> N - 1

ii. From j = i to N where you will traverse complete array
iii. Now 3rd loop for maintain sum
iv. Then keep track if sum == k then maintain maxi

int n = [Link]();
int maxi = 0;
for(int i = 0; i < n; i++){
for(int j = i; j < n; j++){
int sum = 0;
for(int t = i; t <= j; t++){
 sum +=arr[t];
}
if(sum == k){
maxi = max(maxi,j - i + 1);
}
}
}

return maxi;

Approach 2: Better Approach

i. From 0 to N where i = 0 ---> N - 1
ii. From j = i to N where you will traverse complete array
iii. Don’t maintain 3rd loop instead do sum+=arr[j]

int n = [Link]();
int maxi = 0;
for(int i = 0; i < n; i++){
int sum = 0;
for(int j = i; j < n; j++){
sum+=arr[j];
if(sum == k){
maxi = max(maxi,j - i + 1);
}
}
}

Approach 3: Optimal Approach ( by using HashMap)

KEY IDEA:

 Use Prefix Sum + HashMap to solve in O(n) instead of brute force O(n²)

 If (Sum - k) was seen before at index j, then subarray from j+1 → i sums to k

 Map stores { sum → first index seen } — first index only, so we always get the longest
window

int n = [Link]();
unordered_map<int,int>mpp;
int maxi = 0;
int sum = 0;
for(int i = 0; i < n; i++){
 sum+=arr[i];
if(sum == k){
maxi = max(maxi, i+1 );
}
long long remains = sum - k;
if([Link](remains) != [Link]()){
int len = i - mpp[remains];
maxi = max(maxi,len);
}
if([Link](sum) == [Link]()){
mpp[sum] = i;
}
}
return maxi;
}

Question 10: Find the Majority Element that occurs more than
N/2 times
WHAT TO DO: Find the element that appears more than n/2 times in the array.

Example: Input: nums = [2, 2, 1, 1, 2, 2, 2], n = 7

Output: 2
Reason: 2 appears 5 times → 5 > 7/2 = 3 → 2 is the majority element.

WHAT I DID IN SIMPLE WORDS:

Step 1 → Count frequency of every element using a HashMap
Step 2 → Loop through the map and check whose frequency is greater than n/2
Step 3 → Return that element

unordered_map<int,int> mpp; // stores {element → frequency}

// Step 1: count frequency of each element

for(int i = 0; i < n; i++){
mpp[nums[i]]++; // increment count of nums[i]
}
// Step 2: find who has frequency > n/2
for(auto it: mpp){
if([Link] > (n/2)){ // [Link] = element, [Link] = frequency
return [Link]; // this is our majority element
 }
}
return -1; // no majority element found

Approach 3: Better Approach

WHAT I DID IN SIMPLE WORDS:

Think of it like an election — the majority candidate survives all the cuts
Pick first element as candidate, give it 1 vote
If next element is same → vote increases
If next element is different → vote decreases (cancel each other out)
If votes hit 0 → current candidate is eliminated, new candidate takes over with count = 1
The last surviving candidate is the majority element
Moore did not win until he survived from cutting

int findMajorityElement(int arr[], int n) {

int element = arr[0];
int cnt = 1;
for(int i = 1; i < n; i++){
if(arr[i] == element){
cnt ++;
}else{
cnt--;
}
if (cnt == 0){
element = arr[i];
cnt = 1;
}
}
int cnt1=0;
for(int i = 0; i < n; i++){
if(arr[i] == element){
cnt1++;
}
}
if(cnt1 > (n/2)){
return element;
}
return -1;
}
Question 11: Kadane's Algorithm : Maximum Subarray Sum in
an Array 🔁
WHAT TO DO: Find the contiguous subarray which has the largest sum and return that sum.

Example: Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] Output: 6 Subarray: [4, -1, 2, 1] → 4 + (-1) + 2
+1=6

WHAT I DID IN SIMPLE WORDS:

Keep adding elements to the current sum
Whenever current sum beats the best sum → update best answer and save that
subarray
If current sum goes negative → it is a burden, reset it to 0 and start fresh
Kadane always resets the sum — a negative sum never helps, dump it and restart
Think of it like a shopkeeper — if your running balance goes negative, close that account
and open a new one!

int maxSubArray(vector<int>& nums) {

//kadane algo : remember you have to take sum > 0
// kadane always reset the sum
int n = [Link]();
int sum = 0;
int maxi = INT_MIN;
vector<int>ans;
vector<int>bestans;
for(int i = 0; i < n; i++){
sum+=nums[i];
ans.push_back(nums[i]);
if(sum > maxi){
maxi = sum;
bestans = ans; //here we are taking track of array
}
if(sum < 0){
sum = 0;
[Link]();
}
}

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

cout<<bestans[i]<<" ";
}
return maxi;
Question 13: Best Time to Buy and Sell Stock
WHAT TO DO: Given an array of prices where prices[i] is the price on day i, find the maximum
profit you can make by buying on one day and selling on a later day.

Example: Input: prices = [7, 1, 5, 3, 6, 4] Output: 5

Reason: Buy on day 2 (price=1) → Sell on day 5 (price=6) → Profit = 6-1 = 5

WHAT I DID IN SIMPLE WORDS:

Keep track of the minimum price seen so far (best day to buy)
At every day, calculate profit if you sold TODAY minus the cheapest buy so far
Keep updating the maximum profit found
📉📈 Always buy at the valley, sell at the peak — but you only know the valley when
you've passed it!
Think of it like shopping — you always wish you had bought at the lowest price you've
seen so far

int maxProfit(vector<int>& prices) {

int mini = prices[0];
int maxi = 0;
int n = [Link]();
int profit = 0;
for(int i = 1; i < n; i++){
mini = min(mini,prices[i]);
profit = prices[i] - mini;
maxi = max(maxi,profit);
}
return maxi;
}
};

Question 14: Find Subarray with Maximum Sum (No

Negatives) Approach: Modified Kadane's Algorithm
WHAT TO DO: Find the contiguous subarray with the maximum sum, but here negative numbers
act as hard walls — they completely break the subarray. Return the subarray itself, or {-1} if no
valid subarray exists.

Example: Input: arr = [1, 2, 5, -7, 1, 7] Output: [1, 7] Reason: [1,2,5] = sum 8 vs [1,7] = sum 8 →
both equal sum but [1,7] has more elements → return [1,7]
 WHAT I DID IN SIMPLE WORDS:
Negative numbers are WALLS — the moment you hit one, stop, reset everything and
jump over it
Keep adding positive numbers and building the current subarray
If current sum beats best sum → save it as best answer
If current sum ties best sum BUT current subarray is longer → still update (longer
subarray wins the tie)
🧱 Negatives are walls, not speed bumps — you don't slow down, you fully reset and
restart after every wall

vector<int> findSubarray(vector<int>& arr) {

// code here [1, 2, 5, -7, 1, 7]
int n = [Link]();
vector<int>ans;
int maxi = 0;
int sum = 0;
vector<int>bestans;
for(int i = 0; i < n; i++){
if(arr[i] < 0){
sum = 0;
[Link]();
continue;
}
sum+=arr[i];
ans.push_back(arr[i]);

if(sum > maxi || ( sum == maxi && [Link]() > [Link]())){

maxi = sum;
bestans = ans;
}
}

if([Link]()) return {-1};

return bestans;
}

Question 15: Rearrange Array Elements by Sign

WHAT TO DO: Rearrange array so that positives and negatives alternate, starting with a
positive. Equal number of positives and negatives are guaranteed.
Example: Input: nums = [3, 1, -2, -5, 2, -4] Output: [3, -2, 1, -5, 2, -4] Reason: pos = [3,1,2]
neg = [-2,-5,-4] → alternate → [3,-2, 1,-5, 2,-4]

vector<int> rearrangeArray(vector<int>& nums) {

vector<int>posi;
vector<int>negs;
int n = [Link]();
for(int i = 0; i < n; i++){
if(nums[i] >= 0){
posi.push_back(nums[i]);
}else{
negs.push_back(nums[i]);
}
}

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

nums[2 * i] = posi[i];
nums[2 * i + 1] = negs[i];

return nums;
}

TC: O(n) + O(n)

SC : O(n)
Approach 2: Can you do in one pass

WHAT I DID IN SIMPLE WORDS:

Create a result array of size n filled with 0s

Use two pointers — posi starts at 0 (first even index), neg starts at 1 (first odd index)
Single pass through nums — if positive, place at posi and jump +2, if negative place at
neg and jump +2
🎯 No buckets this time — two pointers racing through even and odd lanes directly!

vector<int> ans(n, 0); // result array prefilled with 0s

int posi = 0; // pointer for even indices (0,2,4...)
int neg = 1; // pointer for odd indices (1,3,5...)
 for(int i = 0; i < n; i++){

if(nums[i] < 0){

ans[neg] = nums[i]; // place negative at odd index
neg += 2; // jump to next odd index
} else {
ans[posi] = nums[i]; // place positive at even index
posi += 2; // jump to next even index
}
}
return ans;

Question 16: Rearrange Array Elements by Sign (Follow up

where posi and negs are not equal.

WHAT TO DO: Same alternating idea but now positives and negatives count may differ.
Alternate as long as both are available, then dump the leftover ones at the end.

Example: Input: a = [1, 2, -4, -5, 3, -1] Output: [1, -4, 2, -5, 3, -1] Reason: pos=[1,2,3] neg=[-4,-5,-
1] → equal here → fully alternate

Input: a = [1, 2, -4, -5, 3] Output: [1, -4, 2, -5, 3] Reason: pos=[1,2,3] neg=[-4,-5] → alternate 2
pairs → leftover pos=[3] appended at end

WHAT I DID IN SIMPLE WORDS:

Separate into pos and neg buckets just like before
Find who has more elements — the smaller one controls how many pairs we alternate
Alternate only for min(pos,neg) pairs
After alternating, whoever had extra elements → just append them at the end one by
one
🏁 Dance in pairs as long as both have partners — whoever is left without a partner waits
at the end of the line!

vector<int> pos, neg;

// Step 1: fill buckets

for(int i = 0; i < n; i++){
if(a[i] > 0) pos.push_back(a[i]);
else neg.push_back(a[i]);
}
 if([Link]() > [Link]()){

// Step 2a: alternate for [Link]() pairs (neg is smaller)

for(int i = 0; i < [Link](); i++){
a[2*i] = pos[i]; // even index → positive
a[2*i+1] = neg[i]; // odd index → negative
}

// Step 3a: append leftover positives

int index = [Link]() * 2; // start right after last pair
for(int i = [Link](); i < [Link](); i++){
a[index++] = pos[i];
}

} else {

// Step 2b: alternate for [Link]() pairs (pos is smaller)

for(int i = 0; i < [Link](); i++){
a[2*i] = pos[i];
a[2*i+1] = neg[i];
}

// Step 3b: append leftover negatives

int index = [Link]() * 2; // start right after last pair
for(int i = [Link](); i < [Link](); i++){
a[index++] = neg[i];
}
}

return a;

Question 17: Next Permutation

WHAT TO DO: Find the next permutation of the array — the next lexicographically greater
arrangement. If already the largest, wrap around to the smallest (just reverse).

Example: Input: [1, 2, 3] → Output: [1, 3, 2] Input: [3, 2, 1] → Output: [1, 2, 3] (largest → wrap
to smallest) Input: [1, 3, 2] → Output: [2, 1, 3]

Approach 1: Brute Force (Recursion) — Generate all permutations, find current, return next
one

 Time: O(n! × n) — too slow, just know it exists

Approach 2: STL — just call next_permutation([Link](), [Link]())

 One liner, but never say this in interviews!

Approach 3: Optimal Implementation

WHAT I DID IN SIMPLE WORDS:

Step 1 → Find the DIP — go from right to left, find first element that is smaller than its
next (that's where the order broke)
Step 2 → From the right, find the next element just greater than the dip and swap them
Step 3 → After swapping, reverse everything after the dip index to get the smallest
possible tail
If no dip found → array is fully descending → just reverse the whole thing. We conclude
that this is last permutation possible and now we will give first one by reversing

void nextPermutation(vector<int>& nums) {

//1. finding the dip
//2. from back check next smallest to dip and swap with it
//3 then you will reverse remaining one after the dip
int n = [Link]();
int index = -1; // we take -1 because if we do not found dip then we will simply
reverse it.
//1. finding dip from n-2 beacause we are checking next to it is greater?
for(int i = n-2; i>=0; i--){
if(nums[i] < nums[i+1]){
index = i;
break;
}
}

//if there is no break point simply reverse the array

if(index == -1){
reverse([Link](),[Link]());
return;
}

// find next smaller to the dip and swap it

for(int i = n-1; i>index; i--){
if(nums[i] > nums[index]){
swap(nums[i],nums[index]);
break;
}
 }

// we are ready with greater. now we want smallest as possible so we reverse next
reverse([Link]() + index + 1, [Link]()); //O(n)

//TC: O(3n)
//SC: O(1)

}
};

Question 18 Leaders in an Array

WHAT TO DO: An element is a leader if nothing to its right is greater than it. The rightmost
element is always a leader.

Example: Input: arr = [16, 17, 4, 3, 5, 2] Output: [17, 5, 2]

Reason: 17 → nothing greater on right ✓, 5 → only 2 on right ✓, 2 → rightmost always leader ✓

Approach 1: Brute Force

WHAT I DID IN SIMPLE WORDS:
For every element, check all elements to its right
If none of them is greater → it is a leader
🔍 Check every element by looking over its shoulder at everyone behind it

// brute_force
int n = [Link]();
vector<int>ans;
for(int i = 0; i < n; i++){
bool isLeader = true;
for(int j = i+1; j < n; j++){
if(arr[i] < arr[j]){
isLeader = false;
break;
}
}
if(isLeader){
ans.push_back(arr[i]);
}
}
 return ans;

// TC: O(N2)
//SC: O(N)

Approach 2: Optimal (Reverse Traversal)

WHAT I DID IN SIMPLE WORDS:
Traverse from RIGHT to LEFT keeping track of maximum seen so far
If current element is greater or equal to max seen → it is a leader, update max
At the end reverse the answer since we collected leaders right to left
👑 Walk from the back — whoever is the tallest seen so far is a leader. New tallest?
Crown them and move on!

vector<int> leaders(vector<int>& arr) {

// code here
int n = [Link]();
int maxi = INT_MIN;
vector<int>ans;
for(int i = n-1; i>=0; i--){ //O(N)
if(arr[i] >= maxi){
ans.push_back(arr[i]);
maxi = arr[i];
}
}
reverse([Link](),[Link]()); //O(N)
return ans;

//TC: O(N) + O(N)

//SC: O(N)--to return ans
}

Question 19 Leaders in an Array

WHAT TO DO: Find the length of the longest sequence of consecutive integers in an unsorted
array.

Example: Input: nums = [100, 4, 200, 1, 3, 2] Output: 4 Reason: After sorting → [1, 2, 3, 4, 100,
200] → longest consecutive chain = [1,2,3,4] → length = 4

Approach 1: Sorting
 WHAT I DID IN SIMPLE WORDS:
Sort the array so consecutive numbers come next to each other
Walk through and keep counting when next element = current + 1
If duplicate found → skip it (don't reset count)
If gap found → reset count to 1
🚶 Sort first, then just walk and count your steps — if the next step is +1 keep going, if
you hit a wall reset!

if([Link]() < 1){

return 0;
}

sort([Link](),[Link]()); // O(nlogn);
int cnt = 1;
int n = [Link]();
int maxi = 1;
for(int i = 1; i < n; i++){ // O(n)
if(nums[i - 1] + 1 == nums[i]){
cnt++;
maxi = max(maxi,cnt);
}else if(nums[i] != nums[i-1]){
cnt = 1;
}
}

return maxi;

//TC: O(n) + O(nlogn) nearby O(n)

Question 20 Rotate matrix by 90 degrees

WHAT TO DO: Rotate an n×n matrix 90 degrees clockwise in-place.

Example:

Input: Output:

1 2 3 7 4 1

4 5 6 → 8 5 2

7 8 9 9 6 3

Approach 1: Extra Matrix (Your Solution)

WHAT I DID IN SIMPLE WORDS:
 Observe where each element goes after 90° rotation
Element at (i, j) lands at (j, n-1-i) in the new matrix
Create a new answer matrix, place every element at its new position
Copy answer matrix back to original
🔭 Observe the pattern on paper first — rotation always follows a fixed formula, just find
it and apply!

(0,0)→(0,2) (0,1)→(1,2) (0,2)→(2,2)

(1,0)→(0,1) (1,1)→(1,1) (1,2)→(2,1)
(2,0)→(0,0) (2,1)→(1,0) (2,2)→(2,0)

Pattern: (i, j) → (j, n-1-i)

// observation as attached image

// we run loop for N and N not N and M because it is N X N matrix
int n = [Link]();
vector<vector<int>>ans(n,vector<int>(n,0));
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){ // as n X n
ans[j][n-1-i] = matrix[i][j]; // it was based on observation
}
matrix = ans;
}md

Approach 2:

WHAT I DID IN SIMPLE WORDS:

Transpose loop now starts j from i+1 (not 0) — only swaps upper triangle
This avoids double swapping and skips the diagonal (no need to swap element with
itself)
Then reverse each row as usual
 📐 Only swap the upper triangle — the diagonal stays, lower triangle automatically
follows!

int n = [Link]();
for(int i = 0; i < n-1; i++){
for(int j = i+1; j< n; j++){
swap(matrix[i][j], matrix[j][i]);
}
}

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

reverse(matrix[i].begin(),matrix[i].end());
}

Question 21 Spiral Matrix

Input: Output:

1 2 3 [1,2,3,6,9,8,7,4,5]

4 5 6 →

7 8 9

WHAT I DID IN SIMPLE WORDS:

Maintain 4 boundaries — top, bottom, left, right
Go RIGHT along top row → shrink top down
Go DOWN along right col → shrink right left
Go LEFT along bottom row → shrink bottom up (only if row still exists)
Go UP along left col → shrink left right (only if col still exists)
Repeat until boundaries cross
🌀 Peel the matrix like an onion — take the outer layer, shrink the boundary, repeat for
inner layers!

// easy iteration method just you have to keep track of top right left bottom
int n = [Link]();
int m = matrix[0].size();
vector<int>ans;

int left = 0; int right = m - 1;

int top = 0; int bottom = n - 1;

while(left <= right && top <= bottom){

// first take first row from left to right
 for(int i = left; i <= right; i++){
ans.push_back(matrix[top][i]);
}

top++;

// now take standing line

for(int i = top; i <= bottom; i++){

ans.push_back(matrix[i][right]);
}

right--;
if(top <= bottom){
// sleeping line
for(int i = right; i>= left; i--){
ans.push_back(matrix[bottom][i]);
}
}

bottom--;
if(left<=right){
// anthor standing line
for(int i = bottom; i >= top; i--){
ans.push_back(matrix[i][left]);
}
}

left++;

return ans;

Question 22 : 3Sum
Brute:
#include <bits/stdc++.h>
using namespace std;

int main() {
string s; getline(cin,s); //HELLO
int k; cin>>k; // 3
int i = 0;
if (k <= 0){
cout<<"invalid";
}

while(s[i] !='\0'){
if(s[i] >= 'A' && s[i] <= 'Z'){
if(s[i] + k <= 'Z'){
s[i] = s[i] + k;
}else{
//in case of y
int left = (s[i] + k) - 'Z';
s[i] = 'A' + left - 1;
}
}else if(s[i] >= 'a' && s[i] <= 'z'){
if(s[i] + k <= 'z'){
s[i] = s[i] + k;
}else{
int left = (s[i] + k) - 'z';
s[i] = s[i] + 'a' - 1;
}
}else if(s[i] >= '0' && s[i] <= '9'){
if(s[i] + k <= '9'){
s[i] = s[i] + k;
}else{
int left = s[i] + k - '9';
s[i] = '0' + left - 1;
}
}
i++;
}
cout<<s<<endl;
}