Forem: Nithya Dharshini official

Cracking "Duplicate Zeros" with 0ms Runtime

Nithya Dharshini official — Wed, 01 Apr 2026 17:23:30 +0000

Just hit that 0ms (100th percentile) milestone on LeetCode! Here is a quick breakdown of how to solve the Duplicate Zeros problem using a clean "Buffer" strategy.

The Challenge

Duplicate every 0 in a fixed-length array while shifting other elements to the right. Anything pushed beyond the original array size is discarded.

Example:

Input: [1, 0, 2, 3, 0, 4, 5, 0]
Output: [1, 0, 0, 2, 3, 0, 0, 4]

The Strategy: Speed Over Space

While the "ideal" interview answer is an in-place, two-pointer approach O(1) space, I used a Buffer Strategy O(n) space:
The Buffer: I created a temporary vector to store the result.
The Logic: Iterate through the array. If it's a 0, push two. If not, push one.
The Sync: Overwrite the original array.

The Code (C++)

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        vector<int> res;
        for(int x : arr) {
            if(x == 0) {
                res.push_back(0); res.push_back(0);
            } else {
                res.push_back(x);
            }
        }

        // Overwrite in-place as requested (using our buffer)
        for(int i = 0; i < arr.size(); ++i) {
            arr[i] = res[i];
        }
    }
};

Performance vs. Requirements

My Runtime: 0 ms (Beats 100%)
The Constraint: "Do it in place."

Is it wrong? Technically, it violates the O(1) space constraint usually intended by "in-place."
Is it fast? Absolutely. Modern memory allocation and linear copying are so optimized that this approach often outperforms complex pointer logic on small-to-medium datasets.

Takeaway

In a real interview, I'd explain the O(1) space-optimal approach (iterating backward), but in a production environment, sometimes the most readable code is the best code.How do you feel about using extra space to gain performance? Let’s debate in the comments!

[Boost]

Nithya Dharshini official — Sun, 29 Mar 2026 14:45:42 +0000

Partition Labels – Greedy + Two Pointer Thinking

Nithya Dharshini official — Thu, 26 Mar 2026 15:53:39 +0000

This problem looks confusing at first…
“Split the string so each character appears in only one part” . But once you see the pattern, it becomes very clean.

Key Idea

Each character has a last occurrence in the string.
-> If you know how far a character goes,
you can decide where to cut the partition

Approach (Simple Thinking)

Step 1: Store last position of each character

last[s[i] - 'a'] = i;

Now you know:
-> where each character must end

Step 2: Traverse and expand partition

Start from index 0
Keep updating end = farthest last occurrence seen so far
end = max(end, last[s[i] - 'a']);
Step 3: When i == end

You found a valid partition store its length start a new partition

Code (C++)

class Solution {
public:
    vector<int> partitionLabels(string s) {
        vector<int> last(26);

        //step 1:store last index
        for(int i = 0; i < s.size(); i++) {
            last[s[i] - 'a'] = i;
        }

        vector<int> res;
        int start = 0, end = 0;

        //step 2:expand window
        for(int i = 0; i < s.size(); i++) {
            end = max(end, last[s[i] - 'a']);

            //step 3:cut partition
            if(i == end) {
                res.push_back(end - start + 1);
                start = i + 1;
            }
        }

        return res;
    }
};

Example

Input: -> "ababcbacadefegdehijhklij"

Output: -> [9, 7, 8]

How to Think

Treat it like a window
Expand until all characters are “safe”
When no future dependency -> cut

Complexity

Time: O(n)
Space: O(1) (26 characters only)

What I Learned

Not all problems are pure two-pointer
This is more like greedy + window expansion
Tracking last occurrence is the key trick

Two Sum IV – Input is a BST (Two Pointer Approach)

Nithya Dharshini official — Thu, 19 Mar 2026 15:47:10 +0000

We already know the classic Two Sum problem on arrays.
But what if the data is inside a Binary Search Tree (BST)?

At first, it looks tricky… but we can convert it into something familiar.

Key Idea

A BST inorder traversal gives a sorted array.Once we have a sorted array, we can apply:
-> Two Pointer Technique

Approach

Step 1: Convert BST → Sorted Array
Use inorder traversal

Left → Root → Right

This guarantees sorted order.

Step 2: Apply Two Pointers

left = 0 , right = n - 1

Then:

If sum == target -> return true
If sum < target -> move left++
If sum > target -> move right--

Why This Works

BST property -> inorder gives sorted values
Sorted values -> perfect for two pointer optimization

So we reduce:

Tree problem -> Array problem

Code (C++)

class Solution {
public:
    void inorder(TreeNode* root, vector<int>& arr) {
        if (root == NULL) return;

        inorder(root->left, arr);
        arr.push_back(root->val);
        inorder(root->right, arr);
    }

    bool findTarget(TreeNode* root, int k) {
        vector<int> arr;
        inorder(root, arr);

        int left = 0, right = arr.size() - 1;

        while (left < right) {
            int sum = arr[left] + arr[right];

            if (sum == k) return true;
            else if (sum > k) right--;
            else left++;
        }

        return false;
    }
};

Example

Input:

root = [5,3,6,2,4,null,7]
k = 9

Sorted array:

[2, 3, 4, 5, 6, 7]

Check pairs:

2 + 7 = 9

Complexity

Time: O(n)
Space: O(n) (for array)

What I Learned

Tree problems can be simplified using traversal
Converting to array helps reuse known patterns
Two pointer works beautifully on sorted data

Final Thought

Sometimes the best trick is:
-> Convert the problem into something you already know

Tree -> Array
Array -> Two Pointer

Done.

Remove Duplicates from Sorted Array II (LeetCode 80) — Simple Explanation

Nithya Dharshini official — Tue, 17 Mar 2026 15:59:40 +0000

This problem is a great extension of the basic two-pointer technique.

Problem Understanding

We are given a sorted array.
-> We must remove duplicates in-place
-> But each element can appear at most twice

Example

Input: -> [1,1,1,2,2,3]

Output: -> [1,1,2,2,3]

Return: -> k = 5

Idea (Very Simple)

We use two pointers:

j -> reads elements
k -> writes valid elements

Key Condition
if (k < 2 || nums[j] != nums[k - 2])

What does this mean?
First 2 elements are always allowed

After that:
Compare current element with 2 positions before

If same -> skip 
If different -> include

Why k - 2?

Because we allow maximum 2 duplicates so we check “Did we already take this number twice?”

C++ Code

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int k = 0;

        for (int j = 0; j < nums.size(); j++) {
            if (k < 2 || nums[j] != nums[k - 2]) {
                nums[k] = nums[j];
                k++;
            }
        }

        return k;
    }
};

Dry Run (Important)

Input: -> [1,1,1,2,2,3]

j	nums[j]	k	Action	Result
0	1	0	take	[1]
1	1	1	take	[1,1]
2	1	2	skip	[1,1]
3	2	2	take	[1,1,2]
4	2	3	take	[1,1,2,2]
5	3	4	take	[1,1,2,2,3]

Complexity

Time Complexity : O(n)

Space Complexity : O(1)

No extra array used

What I Learned

Two-pointer technique is very powerful
Instead of counting duplicates, we can control placement
k - 2 trick ensures at most 2 duplicates

Understanding Prefix Sum with a Practical Example (Pocket Money Tracker)

Nithya Dharshini official — Tue, 10 Mar 2026 16:52:24 +0000

Prefix Sum is a simple but powerful technique used in many array problems instead of recalculating sums repeatedly, we store running totals to answer queries instantly.Let’s understand this using a small real-life example.

The Scenario: Pocket Money Tracker

Imagine you are tracking your daily expenses for a week.You store them in an array:

expenses = [10, 20, 5, 15, 30, 10, 50]

Each number represents the amount spent on that day.

Day	Expense
0	10
1	20
2	5
3	15
4	30
5	10
6	50

Now your friend asks questions like:

How much did you spend from Day 2 to Day 4?
What was the total from Day 0 to Day 5?

If you calculate this every time using a loop, it becomes inefficient. This is where Prefix Sum helps.

Step 1: Build the Prefix Sum Array

Prefix sum stores the running total of expenses.

Formula:

prefix[i] = prefix[i-1] + expenses[i]

Result:

Day	Prefix Sum
0	10
1	30
2	35
3	50
4	80
5	90
6	140

So the prefix array becomes: -> [10, 30, 35, 50, 80, 90, 140]

Step 2: Answer Queries Instantly

Now suppose we want the total from Day 2 to Day 4.

Instead of adding: 5 + 15 + 30

We simply do: prefix[4] - prefix[1]

Which gives: 80 - 30 = 50 (Instant answer ^-^)

C++ Implementation

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

int main() {
    vector<int> v = {10, 20, 5, 15, 30, 10, 50};
    int L = 2, R = 4; 

    vector<int> pref(v.size());
    pref[0] = v[0];

    for(int i = 1; i < v.size(); ++i) {
        pref[i] = pref[i-1] + v[i];
    }

    int result = (L == 0) ? pref[R] : pref[R] - pref[L-1];

    cout << "Total spending: " << result << endl;

    return 0;
}

Output: -> 50

Why Prefix Sum is Powerful

Without Prefix Sum: Each query → O(n)
With Prefix Sum: Each query → O(1)

This is extremely useful when we have many range queries.

Key Takeaway

Prefix Sum is useful when:

You need sum of elements in a range
There are multiple queries
You want fast lookup instead of repeated loops

It is widely used in:

Data analytics
Financial calculations
Competitive programming
Range query problems

Battery Optimization Mode – A Custom Sliding Window Problem(Real World Example)

Nithya Dharshini official — Mon, 09 Mar 2026 16:52:01 +0000

Problem

Smart glasses run heavy processing tasks like real-time navigation or object detection.Each minute the processor consumes some power.

We are given:

An array power_drain each value represents power consumption per minute (mW).A power_budget which is the maximum safe power usage. Our goal:

-> Find the maximum number of consecutive minutes the glasses can run without exceeding the power budget.

Example

Input

power_drain = [3, 1, 2, 7, 4, 2, 1, 1, 5]
power_budget = 8

Output

Explanation

The longest valid subarray is:

[4, 2, 1, 1]

Sum = 8
Length = 4 minutes

Approach — Variable Sliding Window

We use two pointers:

left → start of window
right → end of window

Steps:

Expand the window by moving right
Add the current power consumption
If the total exceeds the budget, shrink from left
Track the maximum window length
This technique avoids recalculating sums repeatedly.

C++ Implementation

#include <iostream>
#include <vector>

using namespace std;

int main() {

    vector<int> power_drain = {10, 5, 2, 1, 4};
    vector<int> st;

    int power_budget = 4;
    int result = 0;

    int left = 0;
    int minSum = 0;

    for(int right = 0; right < power_drain.size(); right++) {

        st.push_back(power_drain[right]);
        minSum += power_drain[right];

        while(minSum > power_budget) {
            st.erase(st.begin());
            minSum -= power_drain[left];
            left++;
        }

        result = max(result, (int)st.size());
    }

    cout << result;

    return 0;
}

Complexity

Time Complexity - O(n)
Each element enters and leaves the window at most once.

Space Complexity - O(n)
Because we store the current window.

Key Idea

This is called a Variable Sliding Window because the window expands and shrinks depending on the condition.

Condition here:

window_sum <= power_budget

If it exceeds the budget → shrink from the left.

What This Problem Teaches

Real world usage of Sliding Window
Efficient way to find longest subarray with sum ≤ k
Using two pointers technique

This pattern is very common in problems related to:

battery usage
network bandwidth
memory allocation
CPU utilization

Sliding Window on a Circular Array — Defuse the Bomb (LeetCode 1652)

Nithya Dharshini official — Thu, 05 Mar 2026 17:06:24 +0000

Today I solved an interesting Sliding Window problem on a circular array.This problem helped me understand how sliding windows work when the array wraps around.

Problem Summary

We are given:

A circular array code and an integer k. We must replace each element with a sum of other elements depending on k.

Rules:

If k > 0 → sum of the next k elements
If k < 0 → sum of the previous |k| elements
If k = 0 → result is 0

Important:
The array is circular.That means:

code[n-1] → next element is code[0]
code[0] → previous element is code[n-1]

Example

Input: -> code = [5,7,1,4] , k = 3
Result: -> [12,10,16,13]

Because:

5 → 7 + 1 + 4 = 12
7 → 1 + 4 + 5 = 10
1 → 4 + 5 + 7 = 16
4 → 5 + 7 + 1 = 13

Idea

Instead of recalculating sums again and again, we use a Sliding Window.

Steps:

Build the first window sum.
Slide the window.
Remove the leaving element.
Add the entering element.
Because the array is circular, we use:
index % n
to wrap around the array.

C++ Implementation

class Solution {
public:
    vector<int> decrypt(vector<int>& code, int k) {
        vector<int> v(code.size(),0);
        int n = code.size();

        if(k == 0) return v;

        int start = (k > 0) ? 1 : n + k;
        int end   = (k > 0) ? k : n - 1;

        int winSum = 0;

        for(int i = start; i <= end; ++i){
            winSum += code[i];
        }

        for(int i = 0; i < n; ++i){
            v[i] = winSum;

            winSum -= code[start % n];
            winSum += code[(end + 1) % n];

            start++;
            end++;
        }

        return v;
    }
};

Complexity

Time Complexity - O(n)
We traverse the array only once.

Space Complexity - O(n)
For storing the result.

What I Learned

Sliding Window can work on circular arrays
% n helps wrap indexes
Instead of recalculating sums, we update the window efficiently

Small problem, but a great practice for advanced sliding window thinking.

Understanding Happy Number (LeetCode 202) – HashSet + Cycle Detection

Nithya Dharshini official — Wed, 04 Mar 2026 17:10:43 +0000

Today I solved a classic problem that looks simple but teaches an important concept: cycle detection using a HashSet.

Problem Summary

A number is called a Happy Number.If replace the number with the sum of squares of its digits.Repeat the process if it eventually becomes 1, it is happy.If it enters a loop and never reaches 1, it is not happy.

Example

Input:-> n = 19

Process:

1² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1² + 0² + 0² = 1

Since it reaches 1, the answer is true.

Key Idea

1) The tricky part is:

-> Some numbers fall into an infinite cycle.

2) So how do we detect that?

3) We store already seen numbers inside a HashSet.

4) If a number repeats → we are in a cycle → return false.

C++ Implementation

class Solution {
private:
    int SqrtOfSum(int n){
        int sum = 0;
        while(n > 0){
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
        return sum;
    }

public:
    bool isHappy(int n) {
        unordered_set<int> ust;

        while(n != 1 && ust.find(n) == ust.end()){
            ust.insert(n);
            n = SqrtOfSum(n);
        }

        return n == 1;
    }
};

Complexity

Time Complexity: O(log n) (digit processing repeatedly)
Space Complexity: O(log n) (numbers stored in set)

What I Learned

How to break a number into digits using % 10 and / 10.
How to detect cycles using unordered_set.
Not all loops are obvious — sometimes you must detect them manually.
Simple problem, powerful concept.

From Prefix Array to Clean Variables – LeetCode 1732 (Find the Highest Altitude)

Nithya Dharshini official — Tue, 24 Feb 2026 16:40:06 +0000

Today I solved a simple but important prefix-sum type problem.

Problem Summary

A biker starts at altitude 0.You are given an array gain where:
gain[i] = net altitude change from point i to i+1. We must return the highest altitude reached during the trip.

Example

Input:

gain = [-5, 1, 5, 0, -7]

Altitude journey:

Start: 0
0 + (-5) = -5
-5 + 1 = -4
-4 + 5 = 1
1 + 0 = 1
1 + (-7) = -6

Highest altitude = 1

What I Tried First (Correct but Unnecessary)

I created a full prefix array.

class Solution {
public:
    int largestAltitude(vector<int>& gain) {
        vector<int> prefix(gain.size(),0);
        prefix[0]=gain[0];
        int temp=INT_MIN;

        for(int i=1;i<gain.size();++i){
            prefix[i] = prefix[i-1]+gain[i];
        }

        for(int x : prefix){
            temp=max(x,temp);
        }

        if(temp < 0) return 0;
        return temp;
    }
};

Why this works:

It builds cumulative altitude.Then finds the maximum.

Why it's unnecessary:

We don't need to store all prefix values.We only need the current altitude and maximum altitude.

What I Learned (Cleaner Approach)

We can solve it using just two variables.

class Solution {
public:
    int largestAltitude(vector<int>& gain) {
        int current_altitude = 0;
        int max_altitude = 0;

        for (int g : gain) {
            current_altitude += g;
            max_altitude = max(max_altitude, current_altitude);
        }

        return max_altitude;
    }
};

Why This Is Better

No extra array
No second loop
Cleaner logic
More memory efficient

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Key Takeaway

This problem teaches an important lesson:

Prefix sum does NOT always mean creating a prefix array.Sometimes, a simple running variable is enough.Small problem, but big clarity moment.

Mastering Fixed Sliding Window in C++ (LeetCode 1876)

Nithya Dharshini official — Mon, 23 Feb 2026 16:18:39 +0000

Today I solved a beautiful Sliding Window problem that perfectly demonstrates how fixed-size windows work.

Problem:

Count substrings of size 3 with all distinct characters.

Problem Understanding

We are given a string s. We need to count how many substrings of length 3 contain all distinct characters.

Example

Input:

s = "xyzzaz"

Valid substrings of length 3:

"xyz"

"yzz" (z repeated)

"zza"

"zaz"

Output:

Why Sliding Window?

Since the substring size is fixed (3), this is a Fixed Sliding Window problem.
Instead of generating all substrings (which would be inefficient), we:
Maintain a window of size 3.
Use a frequency map to track character counts.
Slide the window one step at a time.
Check if all characters are distinct.

Approach

Step 1 -> Initialize first window (size 3)

Add first 3 characters into a hashmap.

Step 2 -> Check validity

If all frequencies are 1 → count it.

Step 3 -> Slide the window

For every next position

Remove left character
Add new right character
Check validity again
Repeat until the end.

C++ Implementation

class Solution {
private:
    void counter(unordered_map<char,int>& umap, int& count){
        bool res = true;
        for(auto it : umap){
            if(it.second > 1){
                res = false;
                break;
            }
        }
        if(res) count++;
    }

public:
    int countGoodSubstrings(string s) {
        int count = 0;
        unordered_map<char,int> umap;

        // First window
        for(int i = 0; i < 3; i++)
            umap[s[i]]++;

        counter(umap, count);

        // Slide window
        for(int i = 3; i < s.size(); i++){
            umap[s[i-3]]--;
            umap[s[i]]++;

            counter(umap, count);
        }

        return count;
    }
};

Complexity Analysis

Time Complexity: O(n) -> Each character is processed once.
Space Complexity: O(1)

Window size is fixed (at most 3 characters in map).

Optimization Tip

Since window size is always 3, we can simplify the check . Instead of iterating over the entire map, we can just check:

if(umap.size() == 3)
    count++;

Because if all characters are distinct, the map size will be 3.Cleaner and faster.

What I Learned

-> Fixed window problems are simpler than variable window problems.

-> Frequency maps help validate constraints efficiently.

-> Sliding window avoids brute-force substring generation.

-> Small problem. Big pattern clarity.

Find Pivot Index (Prefix Sum Made Simple)

Nithya Dharshini official — Sat, 21 Feb 2026 17:52:58 +0000

The Pivot Index of an array is the index where:

Sum of elements on the left = Sum of elements on the right
If no such index exists, return -1.

Key Idea

1) Instead of calculating left and right sums again and again (which is slow), we can
2) Compute the total sum of the array.
3) Keep a running left sum. At each index:
-> Right sum = totalSum - leftSum - nums[i]
-> If leftSum == rightSum, that index is the pivot.

This avoids nested loops and makes the solution efficient.

Efficient Approach (Prefix Logic)

Steps:

Find total sum.
Traverse the array.
At each index:

Check if left sum equals right sum.
Update left sum.

C++ Implementation

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int totalSum = 0;
        for (int num : nums)
            totalSum += num;

        int leftSum = 0;

        for (int i = 0; i < nums.size(); i++) {
            if (leftSum == totalSum - leftSum - nums[i])
                return i;

            leftSum += nums[i];
        }

        return -1;
    }
};

Example

Input: [1, 7, 3, 6, 5, 6]

At index 3: -> Left sum = 1 + 7 + 3 = 11 . -> Right sum = 5 + 6 = 11

So output: 3

Complexity

Time    O(n)
Space   O(1)

Final Takeaway

This problem teaches: How to use prefix sum thinking, How to avoid unnecessary recomputation, How to optimize from O(n²) to O(n)

Simple logic. Clean thinking. Efficient solution. 💪