DEV Community: Jaspreet singh

Best Time to Buy and Sell Stock

Jaspreet singh — Tue, 02 Jun 2026 16:10:23 +0000

Given an array where prices[i] represents the stock price on the i-th day, find the maximum profit you can achieve by buying once and selling once in the future.

Example:

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

Explanation:

Buy at 1
Sell at 6

Profit = 6 - 1 = 5

My First Thought (Brute Force)

For every day, I can assume it is the buying day.

Then I can check every future day as a potential selling day and calculate the profit.

Finally, I'll keep track of the maximum profit seen so far.

Brute Force Code

class Solution {
    public int maxProfit(int[] prices) {

        int maxProfit = 0;

        for (int buy = 0; buy < prices.length; buy++) {

            for (int sell = buy + 1; sell < prices.length; sell++) {

                int profit = prices[sell] - prices[buy];

                maxProfit = Math.max(maxProfit, profit);
            }
        }

        return maxProfit;
    }
}

Complexity

Time Complexity: O(N²)
Space Complexity: O(1)

While this works, we're checking many unnecessary buy-sell combinations.

The Key Observation

Let's look at:

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

When I reach a particular day, I don't actually care about all previous prices.

I only care about:

The minimum stock price seen so far.

For example:

Current Price = 6
Minimum Price Seen = 1

Profit = 6 - 1 = 5

To maximize profit at any day:

Profit = Current Price - Minimum Price Seen So Far

This means we don't need nested loops.

We just need to keep track of the cheapest buying opportunity encountered so far.

A DP Thought I Had

Initially, I thought about creating:

dp[i] = Maximum profit till index i

Something like:

dp[i] = Math.max(
    dp[i - 1],
    prices[i] - minPriceTillNow
);

But after thinking deeper, I realized that the most important information isn't the previous profit.

It's actually:

Minimum price seen so far

Since only the minimum value matters, the DP array can be compressed into just two variables.

This makes the problem more of a Prefix Minimum pattern than a Dynamic Programming problem.

Optimal Solution

Maintain:

minPrice  -> cheapest stock seen so far
maxProfit -> best answer so far

For every day:

Calculate profit using the current price.
Update the answer.
Update the minimum price seen so far.

Optimal Code

class Solution {
    public int maxProfit(int[] prices) {

        int minPrice = prices[0];
        int maxProfit = 0;

        for (int i = 1; i < prices.length; i++) {

            int profit = prices[i] - minPrice;

            maxProfit = Math.max(maxProfit, profit);

            minPrice = Math.min(minPrice, prices[i]);
        }

        return maxProfit;
    }
}

Complexity

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

Quick Dry Run

prices = [7,1,5,3,6,4]

Price	Min Price	Profit	Max Profit
7	7	0	0
1	1	0	0
5	1	4	4
3	1	2	4
6	1	5	5
4	1	3	5

Answer:

What I Learned

Whenever I see:

Maximum profit
Maximum difference
Best future outcome based on past values

I should ask:

Can I maintain a running minimum or maximum while traversing?

This simple pattern can turn an O(N²) solution into an O(N) solution.

I'm currently solving the Striver SDE Sheet Challenge and documenting my learnings, patterns, mistakes, and interview insights along the way.

LinkedIn: https://www.linkedin.com/in/jaspreetsodhi482/
X (Twitter): https://x.com/Jaspree54799902
GitHub: https://github.com/codewithjaspreet

Sort Colors (Dutch National Flag Algorithm)

Jaspreet singh — Tue, 02 Jun 2026 09:36:00 +0000

Given an array containing only 0, 1, and 2, sort it in-place so that all 0s come first, followed by 1s, and then 2s.

Example:

Input:  [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

My First Thought (Counting Approach)

Since the array contains only three distinct values, I can count the occurrences of 0, 1, and 2 in one pass.

Then, overwrite the array by placing:

All 0s
Then all 1s
Then all 2s

Code

class Solution {
    public void sortColors(int[] nums) {

        int zero = 0, one = 0, two = 0;

        for (int num : nums) {
            if (num == 0) zero++;
            else if (num == 1) one++;
            else two++;
        }

        int index = 0;

        while (zero-- > 0) nums[index++] = 0;
        while (one-- > 0) nums[index++] = 1;
        while (two-- > 0) nums[index++] = 2;
    }
}

Complexity

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

This works perfectly, but the follow-up asks for a one-pass solution.

The Key Observation

Instead of counting first and rewriting later, can we place elements directly into their correct regions while traversing the array?

Since there are only three values, we can maintain three sections:

0s | 1s | Unknown | 2s

This is where the famous Dutch National Flag Algorithm comes in.

Dutch National Flag Algorithm

We use three pointers:

low  -> next position for 0
mid  -> current element
high -> next position for 2

Rules

If nums[mid] == 0

Place it in the 0-region.

swap(low, mid);
low++;
mid++;

If nums[mid] == 1

Already in the correct region.

mid++;

If nums[mid] == 2

Place it in the 2-region.

swap(mid, high);
high--;

Notice that mid does not move here because the element swapped from the right side still needs to be processed.

Optimal Solution

class Solution {
    public void sortColors(int[] nums) {

        int low = 0;
        int mid = 0;
        int high = nums.length - 1;

        while (mid <= high) {

            if (nums[mid] == 0) {

                swap(nums, low, mid);
                low++;
                mid++;

            } else if (nums[mid] == 1) {

                mid++;

            } else {

                swap(nums, mid, high);
                high--;
            }
        }
    }

    private void swap(int[] nums, int i, int j) {

        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Complexity

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

What I Learned

The biggest takeaway wasn't the solution itself, but the pattern.

Whenever I see:

Only 2 or 3 unique values
In-place segregation
One-pass requirement

I should immediately think about partitioning techniques and the Dutch National Flag Algorithm.

This pattern appears frequently in coding interviews and is much more useful than it initially seems.

I'm currently solving the Striver SDE Sheet Challenge and documenting my learnings, patterns, mistakes, and interview insights along the way.

🔗 LinkedIn: https://www.linkedin.com/in/jaspreetsodhi482/
🐦 X (Twitter): https://x.com/Jaspree54799902
💻 GitHub: https://github.com/codewithjaspreet

Maximum Subarray

Jaspreet singh — Tue, 02 Jun 2026 04:36:16 +0000

Given an integer array nums, find the contiguous subarray with the largest sum and return its sum.

My First Thought (Brute Force)

The most straightforward approach is to generate all possible subarrays, calculate their sums, and keep track of the maximum sum encountered.

Brute Force Code

class Solution {
    public int maxSubArray(int[] nums) {

        int maxSum = Integer.MIN_VALUE;

        for (int i = 0; i < nums.length; i++) {

            int sum = 0;

            for (int j = i; j < nums.length; j++) {

                sum += nums[j];
                maxSum = Math.max(maxSum, sum);
            }
        }

        return maxSum;
    }
}

Complexity Analysis

Time Complexity: O(N²)
Space Complexity: O(1)

While this works, we're repeatedly recalculating sums for overlapping subarrays.

The Key Observation

Suppose my running sum becomes negative.

Current Sum = -5
Next Element = 4

If I continue:

-5 + 4 = -1

If I start fresh:

Clearly:

4 > -1

A negative running sum only hurts future subarrays.

This leads to a powerful insight:

If the running sum becomes negative, discard it and start a new subarray.

Kadane's Algorithm

Kadane's Algorithm maintains a running sum while traversing the array.

For each element:

Add it to the running sum.
Update the maximum answer.
If the running sum becomes negative, reset it to 0.

Optimal Solution

class Solution {
    public int maxSubArray(int[] nums) {

        int currentSum = 0;
        int maxSum = Integer.MIN_VALUE;

        for (int num : nums) {

            currentSum += num;

            maxSum = Math.max(maxSum, currentSum);

            if (currentSum < 0) {
                currentSum = 0;
            }
        }

        return maxSum;
    }
}

Complexity Analysis

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

Quick Dry Run

Input:

[-2,1,-3,4,-1,2,1,-5,4]

Element	Running Sum	Max Sum
-2	-2	-2
Reset	0	-2
1	1	1
-3	-2	1
Reset	0	1
4	4	4
-1	3	4
2	5	5
1	6	6
-5	1	6
4	5	6

Answer:

Subarray:

[4, -1, 2, 1]

Takeaway

Kadane's Algorithm is one of those elegant solutions that turns an O(N²) brute-force approach into an O(N) optimal solution through a simple observation:

A negative running sum can never help a future subarray achieve a larger sum.

By discarding bad prefixes and carrying forward only beneficial contributions, we can find the maximum subarray sum in a single pass.

I'm currently solving the Striver SDE Sheet Challenge and documenting my learnings, patterns, mistakes, and interview insights along the way.

LinkedIn: https://www.linkedin.com/in/jaspreetsodhi482/
X (Twitter): https://x.com/Jaspree54799902
GitHub: https://github.com/codewithjaspreet