Forem: Sana Khan

Why Sorted Input Changes Everything in Array Intersection Problems

Sana Khan — Mon, 23 Jun 2025 08:07:43 +0000

Recently, I worked on two different coding problems — one from LeetCode and another from CodeStudio by Coding Ninjas — that both asked for the intersection of two arrays. At first glance, they looked quite similar, but I quickly learned that whether the input arrays are sorted or not changes everything.
In this blog, I’ll walk through the two problems, my thought process, and the simple solutions I implemented without using any fancy data structures like hashmaps.

🧩 Problem 1: Intersection of Two Sorted Arrays (CodeStudio)

🔹 Approach:
Since both arrays were already sorted, I decided to use the two-pointer technique to find common elements efficiently in linear time.

#include <bits/stdc++.h>
vector<int> findArrayIntersection(vector<int> &arr1, int n, vector<int> &arr2, int m)
{
    vector<int> res;
    int i = 0, j = 0;

    while (i < n && j < m) {
        if (arr1[i] == arr2[j]) {
            res.push_back(arr1[i]);
            i++;
            j++;
        }
        else if (arr1[i] < arr2[j]) {
            i++;
        }
        else {
            j++;
        }
    }

    if (res.empty()) {
        res.push_back(-1);
    }

    return res;
}

🧠 Key Insight:
Because the arrays are sorted, we can just walk through them simultaneously and compare elements directly — no need to sort or use extra space.

🧩 Problem 2: Intersection of Two Unsorted Arrays (LeetCode)

🔹 Approach:
Here, the arrays weren’t sorted. So I used a brute-force approach with nested loops. For every element in the first array, I checked for its presence in the second array and added it to the result if found.

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res;
        for(int i = 0; i < nums1.size(); i++){
            int element = nums1[i];
            for(int j = 0; j < nums2.size(); j++){
                if (element == nums2[j]){
                    res.push_back(element);
                    nums2[j] = -1; // mark as visited
                    break;
                }
            }
        }
        return res;
    }
};

🧠 Key Insight:
Since the arrays weren’t sorted, we didn’t have the advantage of two-pointer traversal. Still, by marking visited elements in nums2, I was able to avoid duplicates without using extra space.

🎯 Final Thoughts:

What surprised me most was how the sorted nature of the array entirely changed the optimal approach. Initially, I didn’t even realize one of the problems had sorted arrays — which led me to use a less efficient brute-force method at first.
Lesson learned: Always read the constraints carefully. Sometimes the presence (or absence) of something as simple as sorting can shift your entire approach — from nested loops to linear two-pointer techniques!

✍️ First Attempt: Reversing Using a Temporary Array

Sana Khan — Sun, 22 Jun 2025 13:03:35 +0000

This is the approach many beginners (myself included) think of first:
“Why not create a new array and fill it in reverse order?”

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

void reverseArray(vector<int> &arr) {
    int n = arr.size();
    vector<int> temp(n);

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

    for (int i = 0; i < n; i++)
        arr[i] = temp[i];
}

int main() {
    vector<int> arr = {1, 4, 3, 2, 6, 5};
    reverseArray(arr);

    for (int val : arr)
        cout << val << " ";
}

🔍 Analysis
✅ Simple and readable
❌ Not memory-efficient – It uses an extra array of the same size (O(n) space)

✅ Optimal Approach: In-Place Reversal Using Swapping

Then I explored another way—swapping elements from both ends of the array until the middle is reached.

void reverseArray(vector<int>& arr) {
    int left = 0, right = arr.size() - 1;
    while (left < right) {
        swap(arr[left], arr[right]);
        left++;
        right--;
    }
}

Or Using a For Loop:

void reverseArray(vector<int>& arr) {
    for (int i = 0; i < arr.size() / 2; i++) {
        swap(arr[i], arr[arr.size() - 1 - i]);
    }
}

🔍 Analysis
✅ Efficient – Reverses the array in O(n) time and O(1) space
✅ Professional standard – Used in interviews and real-world problems
✅ Doesn't require extra memory

LeetCode 231: Power of Two

Sana Khan — Sat, 21 Jun 2025 05:14:05 +0000

🪜 Step 1: My Initial Solution – Converting to Binary

My first thought was:
A number is a power of two only if its binary representation contains exactly one ‘1’.
So I wrote a function to convert a number to its binary form and then counted how many 1s it had.

class Solution {
public:
    string set_bit(int num){
        if (num == 0) return "0";
        string bin = "";
        while (num > 0){
            int rem = num % 2;
            bin += to_string(rem);
            num = num / 2;
        }
        return bin;  // binary in reverse order
    }

    bool isPowerOfTwo(int n) {
        string bits = set_bit(n);
        int count = 0;
        for (int i = 0; i < bits.length(); i++){
            if (bits[i] == '1') count++;
        }
        return count == 1;
    }
};

It worked! Even though the binary string is reversed, it didn’t matter since I only cared about the number of 1s.
✅ What I Learned:

How to convert a number to binary using %
How to analyze the number of set bits (1s).

🧠 Step 2: A Cleaner Way – Count Set Bits Without Strings

While reviewing other solutions, I realized I didn’t need to build a binary string at all. I could count the set bits directly while dividing the number.

Here’s the improved solution:

class Solution {
public:
    bool isPowerOfTwo(int n) {
        if (n <= 0) return false;
        int count = 0;

        while (n > 0) {
            if (n % 2 == 1) count++;  // count set bits
            n /= 2;
        }

        return count == 1;
    }
};

Much better! This avoids unnecessary string manipulation and directly counts the 1s.

💥 Step 3: The Most Efficient Way – Bit Manipulation Trick

Finally, I stumbled upon this line of genius:

return n > 0 && (n & (n - 1)) == 0;

This is the most optimized and elegant solution to check if a number is a power of two. But… how does it work?
🔍 How n & (n - 1) == 0 Works
Example 1:
n = 8 → binary = 1000
n - 1 = 7 → binary = 0111
so (8&7)==0 is true,
and 8>0 is also true ie n > 0 && (n & (n - 1)) gives 1. ✅ result is 1 → so 8 is a power of 2

Example 2:
n = 6 → binary = 1100
n - 1 = 5 → binary = 1010
so (6&5)==0 is false,
and 6>0 is true ie n > 0 && (n & (n - 1)) gives 0. ✅ result is 0 → so 6 is not a power of 2
🧠 Why This Works:
A power of two has exactly one set bit. Subtracting 1 from it flips that bit and all bits to the right of it.
So n & (n - 1) results in 0 only if n had just one set bit.

Here’s the final optimized version:

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }
};

💻 Understanding Arrays in C++ Classes: A Student Score Program

Sana Khan — Wed, 18 Jun 2025 06:52:14 +0000

In this blog, I’ll walk you through a simple yet effective C++ program that uses classes and objects to manage student scores and determine how many students scored more than the first student.

Let’s break it down together! 🧩

🧠 Problem Statement

We have a group of students. Each student gives five test scores. We want to calculate how many students scored more than the first student.

Simple, right? Now let's dive into how this is achieved using classes in C++.

🧑‍🎓 Creating the Student Class

class Student {
private:
    int scores[5]; // Each student has 5 scores
public:
    void input();
    int calculateTotalScore();
};

We define a class Student to encapsulate the scores and operations.

scores[5] is a fixed-size array holding 5 test scores.

input() allows entering the scores.

calculateTotalScore() adds up the scores.

🖊️ Input Function

void Student::input() {
    for (int i = 0; i < 5; i++) {
        cin >> scores[i];
    }
}

This method allows each student object to take 5 scores as input from the user.

➕ Score Calculation

int Student::calculateTotalScore() {
    int sum = 0;
    for (int i = 0; i < 5; i++) {
        sum += scores[i];
    }
    return sum;
}

This method calculates the total score for each student by summing up their individual scores.

🧮 Main Function Logic

int main() {
    int n;
    cin >> n;
    vector<Student> Students(n);
    int num = 0;

    for (int i = 0; i < n; i++) {
        Students[i].input();
        if (Students[0].calculateTotalScore() < Students[i].calculateTotalScore()) {
            num++;
        }
    }

    cout << num;
}

First, we take the number of students n.
We create a vector of Student objects.
For each student:

We take input for their scores.
We compare their total score with that of the first student.
if it’s greater, we increment num.

Finally, we print how many students scored more than the first student.

Sample Input/ output

Input:

4
100 50 40 80 70
30 40 100 90 80
60 60 60 60 60
70 70 70 70 70

Output:
2

Explanation: First student’s total score = 340.
Student 2 = 340 → not greater.
Student 3 = 300 → less.
Student 4 = 350 → greater.

Only Student 4 scored more → output is 1.

🎯 Learning Outcomes

Writing this program helped me understand some key concepts in C++ that were initially confusing but became clearer as I practiced more. Here’s what I learned:

✅ How to use arrays inside a class: Initially, I wasn’t sure how to declare and access an array as a class member, but implementing scores[5] inside the Student class made it clear.

✅ Objects can be stored in arrays or vectors: I learned that we can create an array or vector of objects like vector Students(n);. This was new and slightly confusing at first because we often only work with single objects, not collections of them.

✅ How vectors work with classes: Using a vector to manage multiple objects made the program more flexible and dynamic. It felt tricky at first, but I now understand how powerful it is when dealing with multiple instances of a class.

✅ Logical comparisons become easier with OOP: Initially, I thought I’d have to compare every student with every other student. But thankfully, the problem only asked me to compare each one with the first student — which simplified the logic a lot and helped me focus more on the object-oriented part.

This task gave me a real confidence boost in using OOP with arrays and vectors, and it made me realize how clean and manageable code becomes once you start thinking in terms of objects rather than just variables.

✨Fixing Integer Overflow in C++ with Circular Indexing

Sana Khan — Fri, 13 Jun 2025 11:06:46 +0000

🌀 I Didn't Know Circular Indexing — Here's What Went Wrong (and How I Fixed It)

When I first saw a simple problem — “Find the sum of every 4 consecutive elements in an array of 5 elements, wrapping around circularly” — I thought, "Easy!"

So I wrote my usual loops, added the elements, and printed the results.

It worked… until it didn’t.

That’s when I learned about circular indexing, and even more importantly, integer overflow. Here's how it all unfolded.

🧪 The Problem

Given 5 integers, I needed to calculate 5 sums. Each sum should include 4 consecutive elements from the array, but with wrapping.

For example, given:

The sums should be:

1+2+3+4 = 10
2+3+4+5 = 14
3+4+5+1 = 13 ← wrapped
4+5+1+2 = 12 ← wrapped
5+1+2+3 = 11 ← wrapped

🔨 My First (Flawed) Approach

I began writing the logic like this:

int sum1 = a[0] + a[1] + a[2] + a[3];
int sum2 = a[1] + a[2] + a[3] + a[4];
int sum3 = a[2] + a[3] + a[4] + a[5]; // 🚨 Oops!

That last line? Totally wrong — a[5] doesn’t even exist!
I was trying to access indices beyond the array.

🧭 Discovery: Circular Indexing

After some searching and trial & error, I discovered modulo indexing.
Using % (modulo operator), I could wrap around to index 0 when I go beyond 4.

for (int i = 0; i < 5; i++) {
    for (int j = i; j < i + 4; j++) {
        sum[i] += a[j % 5];  // this wraps around the array
    }
}

🚧 The Next Bug: It Still Broke for Big Inputs

📛 Integer Overflow — I was using int, which can only store up to ~2.1 billion.
So I changed everything to long long.

✅ The Final Code (Bug-Free and Clean)

#include <iostream>
using namespace std;

int main() {
    long long a[5];
    for (int i = 0; i < 5; i++) cin >> a[i];

    long long sum[5] = {0};

    for (int i = 0; i < 5; i++) {
        for (int j = i; j < i + 4; j++) {
            sum[i] += a[j % 5];  // circular indexing
        }
    }

    for (int i = 0; i < 5; i++) {
        cout << sum[i] << endl;
    }

    long long max = sum[0], min = sum[0];
    for (int i = 0; i < 5; i++) {
        if (sum[i] > max) max = sum[i];
        if (sum[i] < min) min = sum[i];
    }

    cout << min << " " << max;
    return 0;
}

Mastering Layered Patterns: A Step-by-Step Guide to Solving Grid and Matrix Challenges with Position-Based Logic

Sana Khan — Sat, 12 Apr 2025 11:30:41 +0000

Sana Khan

Apr 12 '25

🌀 The Spiral Struggle: How I Cracked the Concentric Number Pattern in C

#programming #beginners #tutorial #productivity

Comments

4 min read

🌀 The Spiral Struggle: How I Cracked the Concentric Number Pattern in C

Sana Khan — Sat, 12 Apr 2025 11:30:01 +0000

You know that rush when you finally figure something out after banging your head against a wall for hours? That was me trying to solve a deceptively simple-looking pattern problem in C.

Here’s the challenge:
Problem:
Given a number n, print a (2n-1) x (2n-1) square pattern where the numbers decrease in layers towards the center.

For example, if n = 4, the output should look like this:

4 4 4 4 4 4 4
4 3 3 3 3 3 4
4 3 2 2 2 3 4
4 3 2 1 2 3 4
4 3 2 2 2 3 4
4 3 3 3 3 3 4
4 4 4 4 4 4 4

🧠 Step 1: Overthinking the Basics

First, I tried to figure out the number of rows and columns. You’d think that’s obvious—it’s just 2*n - 1—but I spent way longer than I should have on that. (We all have our moments.)

Once I had that, I did the obvious thing: print a square of that size filled with n.

#include <stdio.h>
int main(){
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= (2*n) - 1; i++){
        for(int j = 1; j <= (2*n) - 1; j++){
            printf("%d ", n);
        }
        printf("\n");
    }
    return 0;
}

Output? A big block of the number n. Cool... but very wrong.

🧱 Step 2: Brute Force Attempts

Then came a new idea: check manually which layer a position falls into and print accordingly. For n = 2, I hardcoded the edges:

int n;
scanf("%d", &n);
for(int i=1; i <= (2*n) - 1; i++){
    for(int j=1; j <= (2*n) - 1; j++){
        if((i==1 || i==(2*n)-1) || (j==1 || j==(2*n)-1)){
            printf("%d ", n);  
        } else {
            printf("%d ", n-1);
        }
    }
    printf("\n");
}

It worked... but only for n=2.

So I extended it manually:

else if((i==2 || i==(2*n)-2) || (j==2 || j==(2*n)-2)) { printf("%d ", n-1); }
else if((i==3 || i==(2*n)-3) || (j==3 || j==(2*n)-3)) { printf("%d ", n-2); }
// and so on...

It started getting messy—really messy. It wasn’t scalable, elegant, or fun anymore.

✨ Step 3: The Breakthrough — It’s Just the Distance from the Edge!

After a ton of brainstorming and frustration, I had a click moment — and it wasn’t from any tutorial or AI assistant. Nobody spelled it out clearly.

I realized: The number we print is just the distance from the nearest edge, subtracted from n.
Not “layers,” not “boundaries,” not “top-left-bottom-right calculations” — just pure distance from the nearest edge.

That’s it.

Let me break it down.

Imagine standing at any position in the square. Ask yourself:
“How close am I to any edge?”

Take the minimum of these:

Distance from the top → i

Distance from the left → j

Distance from the bottom → size - 1 - i

Distance from the right → size - 1 - j

That minimum value is your depth into the square.
And then the number to print is just:
n - depth
Here’s the full code again with this mindset:

#include <stdio.h>
int main(){
    int n;
    scanf("%d", &n);
    int size = (2 * n) - 1;

    for(int i = 0; i < size; i++){
        for(int j = 0; j < size; j++){
            // calculate distance from all four edges
            int top = i;
            int left = j;
            int bottom = size - i - 1;
            int right = size - j - 1;

            // get the minimum distance = depth into the square
            int distance = top;
            if (left < distance) distance = left;
            if (bottom < distance) distance = bottom;
            if (right < distance) distance = right;

            // now subtract from n to get the number to print
            printf("%d ", n - distance);
        }
        printf("\n");
    }
    return 0;
}

💡 Why This Realization Mattered

All the online explanations talked in abstract terms: “layers,” “rings,” “boundaries,” etc.
But none said the simplest, clearest truth:

You're just printing numbers based on how close you are to the nearest edge.

Once I saw it that way, the logic felt natural — like peeling an onion, one layer at a time.

🧠 A Few Little Things I Learned Along the Way

Why bottom = size - i - 1 instead of size - i.
This tripped me up at first — but it’s because array (or loop) indexing starts at 0. So the last row isn’t at index size, it’s at index size - 1. That -1 matters more than you'd think!
Why I used multiple if conditions instead of else if
When calculating layer, we need to find the minimum distance to any edge — top, left, bottom, or right. That means we have to compare all four and keep the smallest one. If I had used else if, it would've skipped checking some of them. Using plain if ensures each comparison is made.
If the pattern was based on a fixed n (already given) rather than dynamic positioning, it would’ve been easier to brute-force with an if-else block like I did earlier. That approach just doesn't scale well or adapt cleanly to any n, which is why understanding the "distance from the edge" concept changed everything.

🧠 More Questions That Use This Approach

Distance from Center Grid Pattern
Square Frame Numbers Pattern
Spiral Matrix Generation
Pattern with Border and Diagonals
Diamond Number Pattern
Layered Star Pattern
Grid with Center Highlighted
Hollow Square with Layers
Symmetric Number Pyramid in a Square Grid