Forem: Partners DSA

Maximizing 1s with a Single Flip: An Elegant Application of Kadane's Algorithm

Partners DSA — Sat, 18 Apr 2026 09:00:49 +0000

Have you ever encountered an algorithmic problem that seems to require a brute-force approach, only to realize it can be transformed into a classic computer science pattern? The "Maximum Ones after at most 1 flip" problem is a perfect example of this.

Instead of checking every possible subarray to flip (which would take a sluggish O(N^2) time), we can reframe the problem and solve it in a blistering O(N) time using Kadane’s Algorithm.

Here is a breakdown of the problem, the core intuition, and a highly optimized Java solution.

The Problem

You are given an array consisting only of 0s and 1s. You are allowed to perform at most one flip operation. A flip operation consists of choosing a contiguous subarray and changing all 0s to 1s and all 1s to 0s.

Your goal is to return the maximum number of 1s you can achieve in the array after this operation.

The "Aha!" Moment: Reframing the Problem

At first glance, it feels like we need to simulate flips. But let's look at what a flip actually does to our total count of 1s:

When we flip a 0, we gain a 1. (Net change: +1)
When we flip a 1, we lose a 1. (Net change: -1)

This means we don't need to count the final 1s directly. We just need to find the contiguous subarray that gives us the maximum net gain. Finding the contiguous subarray with the maximum sum is the exact problem Kadane's Algorithm was built to solve!

The formula for our final answer becomes beautifully simple:
Total 1s = (Initial count of 1s) + (Maximum net gain from a flip)

The Step-by-Step Approach

Count the Baseline: First, we iterate through the array to count how many 1s we start with.
Early Exits (Optimizations): If the array is entirely 0s, flipping the whole array gives us length 1s. If the array is entirely 1s, or only has a single 0, doing zero flips (or flipping that one 0) already maxes out our possible 1s. We can return length immediately and save processing time.
Apply Kadane's: We iterate through the array again. We treat every 0 as a 1 (potential gain) and every 1 as a -1 (potential loss). We use Kadane's algorithm to keep a running sum and track the maximum peak.

The Java Solution

Here is the highly optimized O(N) solution utilizing O(1) space:

class Solution {
    int maxOnes(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }

        int length = arr.length;
        int oneCount = 0;

        // Step 1: Count initial 1s - O(N)
        for (int num : arr) {
            oneCount += num == 1 ? 1 : 0;
        }

        // Step 2: Handle edge cases where max possible 1s is already guaranteed
        // - No 1s (flip everything)
        // - All 1s (0 operations needed)
        // - Only one 0 (flip the single 0)
        if (oneCount == 0 || oneCount == length || oneCount == length - 1) {
            return length;
        }

        // Step 3: Find the maximum net gain using Kadane's Algorithm - O(N)
        int maximumSum = getMaximumSum(arr);

        // Calculate the final total
        int totalCount = oneCount + maximumSum;
        return totalCount < 0 ? 0 : totalCount;
    }

    private int getMaximumSum(int[] arr) {
        int runningSum = 0;
        int maximumSum = Integer.MIN_VALUE;

        for (int num : arr) {
            // Transform: 0 becomes +1 (gain), 1 becomes -1 (loss)
            runningSum += num == 1 ? -1 : 1;
            maximumSum = Math.max(maximumSum, runningSum);

            // If our running sum drops below zero, it's a net loss. 
            // We reset it to 0, effectively starting a new subarray.
            if (runningSum < 0) {
                runningSum = 0;
            }
        }

        return maximumSum;
    }
}

Complexity Analysis

Time Complexity: O(N)
We iterate through the array exactly twice—once to count the initial 1s, and once to calculate the maximum sum. O(2N) simplifies to O(N).

Space Complexity: O(1)
We only use a few primitive integer variables (oneCount, runningSum, maximumSum) to keep track of our state, regardless of how large the input array is.

Mastering the "Sorted Subsequence of Size 3" Problem: Two Efficient Java Approaches

Partners DSA — Fri, 10 Apr 2026 19:22:43 +0000

Finding a sorted subsequence of a specific size is a classic algorithmic challenge that tests your ability to optimize array traversals. The problem asks us to find three elements in an array such that arr[i] < arr[j] < arr[k] and their indices satisfy i < j < k.

If you are preparing for coding interviews or just sharpening your problem-solving skills, this problem is a fantastic way to transition from brute-force thinking to highly optimized logic.

In this post, we will explore two distinct approaches to solving this problem in Java: an intuitive Precomputation Approach and a highly optimized Single-Pass Greedy Approach.

Approach 1: The Prefix and Suffix Arrays (Precomputation)

The Intuition

To find our three numbers, let's focus on the middle element, arr[j]. For any element to act as a valid middle number in our sequence, two conditions must be met:

There must be a strictly smaller number somewhere to its left.
There must be a strictly larger number somewhere to its right.

Instead of scanning the left and right sides over and over for every single element, we can precalculate the smallest numbers on the left and the largest numbers on the right using auxiliary arrays.

How It Works

prefixMin Array: We iterate from left to right, storing the minimum value seen so far at each index.
suffixMax Array: We iterate from right to left, storing the maximum value seen so far at each index.
Once these are built, we simply loop through the original array one last time. For any element arr[i], we check if its corresponding prefixMin[i] is smaller than arr[i] and its suffixMax[i] is larger than arr[i].

The Code

import java.util.ArrayList;
import java.util.Arrays;

class Solution {
    public ArrayList<Integer> find3Numbers(int[] arr) {
        // code here
        if (arr == null || arr.length < 3) {
            return new ArrayList<>();
        }
        int length = arr.length;
        ArrayList<Integer> result = new ArrayList<>();
        int [] prefixMin = new int [length];
        int [] suffixMax = new int [length];
        Arrays.fill(prefixMin, Integer.MAX_VALUE);

        prefixMin[0] = arr[0];
        for (int index = 1; index < length; index++) {
            prefixMin[index] = Math.min(arr[index], prefixMin[index - 1]);
        }

        suffixMax[length - 1] = arr[length - 1];
        for (int index = length - 2; index >= 0; index--) {
            suffixMax[index] = Math.max(arr[index], suffixMax[index + 1]);
        }

        for (int index = 0; index < length; index++) {
            int middleNum = arr[index];
            int leftMin = prefixMin[index];
            int rightMax = suffixMax[index];

            if (leftMin < middleNum && middleNum < rightMax) {
                result.add(leftMin);
                result.add(middleNum);
                result.add(rightMax);
                break;
            }
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(N). We traverse the array exactly three times: once to build prefixMin, once for suffixMax, and one final time to find the sequence. Dropping the constant gives us a linear time complexity.
Space Complexity: O(N). We allocate two additional arrays, each of size N, to store our precomputed boundaries.

Approach 2: The Space-Optimized Single Pass (Greedy)

While the first approach is highly intuitive, creating two additional arrays consumes extra memory. What if the array is massive? We can solve this in a single pass with constant extra space by keeping a running track of the "smallest" and "second smallest" values.

The Intuition

As we iterate through the array, we want to build our sequence dynamically. We can do this by maintaining variables for the smallest element seen so far (verySmall) and the second smallest element (secondSmall).

The tricky part? If we find a new verySmall number, we can't just carelessly overwrite the old one if we already have a secondSmall paired with it. To solve this, this approach brilliantly introduces smallBeforeSecondSmall. This guarantees that when we finally find our third, largest number, we pair it with the exact minimum that historically came before our second-smallest number.

How It Works

Initialize verySmall, secondSmall, and smallBeforeSecondSmall to infinity.
Traverse the array:
- If the current number is smaller than verySmall, update verySmall.
- If it falls strictly between verySmall and secondSmall, update secondSmall and "lock in" the current verySmall into smallBeforeSecondSmall.
- If we find a number strictly greater than secondSmall, we have found our trio!

The Code


class Solution {
    public ArrayList<Integer> find3Numbers(int[] arr) {
        // code here
        if (arr == null || arr.length < 3) {
            return new ArrayList<>();
        }
        int length = arr.length;
        ArrayList<Integer> result = new ArrayList<>();

        int verySmall = Integer.MAX_VALUE;
        int secondSmall = Integer.MAX_VALUE;
        int smallBeforeSecondSmall = Integer.MAX_VALUE;

        for (int num : arr) {
            if (num < verySmall) {
                verySmall = num;
            }
            else if (num > verySmall && num < secondSmall) {
                secondSmall = num;
                smallBeforeSecondSmall = verySmall;
            }
            else if (smallBeforeSecondSmall < secondSmall && secondSmall < num) {
                result.add(smallBeforeSecondSmall);
                result.add(secondSmall);
                result.add(num);
                break;
            }
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(N). We iterate through the array exactly once, performing basic comparison operations at each step.
Space Complexity: O(1). Aside from the output ArrayList, we only use three integer variables, meaning our memory footprint remains constant regardless of the array's size.

Course Schedule: Master Topological Sort with Kahn's Algorithm

Partners DSA — Thu, 09 Apr 2026 15:04:58 +0000

Have you ever looked at a university course catalog and realized you can't take "Advanced Algorithms" without finishing "Data Structures" first? In computer science, this is a Dependency Management problem.

In LeetCode terms, this is the Course Schedule problem, and it's the perfect way to learn about Topological Sorting in Directed Acyclic Graphs (DAGs).

The Problem

Given numCourses and a list of prerequisites (where [a, b] means you must take course b before course a), can you finish all courses?

Basically, we need to check if the graph contains a cycle. If there is a cycle (e.g., A needs B, B needs C, and C needs A), it’s impossible to finish.

The Strategy: Kahn’s Algorithm (BFS)

Kahn’s Algorithm works by looking at the indegree of each node. The indegree is simply the number of incoming edges (dependencies) a node has.

Build an Adjacency List: Represent the courses and their dependencies.
Calculate Indegrees: Count how many prerequisites each course has.
Queue the "Free" Courses: Any course with an indegree of 0 can be taken immediately. Add them to a Queue.
Process the Queue:
- Pick a course, "take" it, and increment your finished count.
- For every neighbor (the courses that depend on this one), decrement their indegree.
- If a neighbor's indegree hits 0, add it to the queue.
Check the Result: If the count of finished courses equals the total number of courses, you're good to go!

Java Implementation

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adjList = new ArrayList<>();
        Queue<Integer> q = new LinkedList<>();

        // 1. Build the Adjacency List
        adjList = buildAdj(numCourses, prerequisites);

        // 2. Calculate Indegrees
        int[] indegree = new int[numCourses];
        for (int i = 0; i < prerequisites.length; i++) {
            indegree[prerequisites[i][0]]++;
        }

        // 3. Add courses with no prerequisites to the queue
        int count = 0;
        for (int i = 0; i < indegree.length; i++) {
            if (indegree[i] == 0) {
                q.add(i);
                count++;
            }
        }

        // 4. BFS Traversal
        while (!q.isEmpty()) {
            int node = q.poll();
            for (int neighbour : adjList.get(node)) {
                indegree[neighbour]--;

                // If dependency count drops to 0, it's ready to be taken
                if (indegree[neighbour] == 0) {
                    q.add(neighbour);
                    count++;
                }
            }
        }

        // 5. If we processed all courses, no cycle exists
        return count == numCourses;
    }

    public List<List<Integer>> buildAdj(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adjList = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            adjList.add(new ArrayList<>());
        }
        for (int i = 0; i < prerequisites.length; i++) {
            // Index 1 is the prerequisite, Index 0 is the course
            adjList.get(prerequisites[i][1]).add(prerequisites[i][0]);
        }
        return adjList;
    }
}

Complexity Analysis

Time Complexity: O(V + E)

We visit every vertex (course) and every edge (prerequisite) exactly once during the adjacency list construction and the BFS traversal.

Space Complexity: O(V + E)

We store the graph in an adjacency list (O(V+E)) and use an indegree array (O(V)) plus a queue (O(V)).

Walking Through the Robot Bounded Box: A Simulation Approach

Partners DSA — Tue, 07 Apr 2026 19:06:52 +0000

Simulation problems are a staple in technical interviews. They test your ability to translate verbal rules into clean, state-driven code. The Robot Bounded Box (or Robot Simulation) problem is a perfect example of this, requiring us to manage directional states and collision logic efficiently.

The Problem at a Glance

We have a robot starting at (0, 0) facing North. We receive a list of commands:

-2: Turn left 90 degrees.
-1: Turn right 90 degrees.
1 to 9: Move forward $X$ units.

Crucially, there are obstacles. If the robot encounters one, it stays in its current position and moves on to the next command. Our goal is to find the maximum squared Euclidean distance the robot ever reaches from the origin.

The Simulation Logic

To solve this efficiently, we focus on three pillars:

1. The Directional Compass

Instead of using complex if-else chains for turning, we use a 2D array to represent the four cardinal directions and an integer direction index.

Turning Right: (direction + 1) % 4
Turning Left: (direction + 3) % 4 (Adding 3 is equivalent to subtracting 1 in modulo 4 math, avoiding negative results).

2. Fast Collision Checking

Checking every obstacle in a list for every single step would be $O(M \times N)$, which is too slow. By converting obstacles into a HashSet of Strings (e.g., "x$y"), we can check for a collision in $O(1)$ time.

3. Step-by-Step Movement

Since we cannot "jump" over obstacles, we move one unit at a time for each movement command, checking the HashSet at every step.

Java Implementation


class Solution {
    // 0: North, 1: East, 2: South, 3: West
    private static final int [][] DIRECTION = new int [][]{
        {0, 1}, {1, 0}, {0, -1}, {-1, 0}
    };

    public int robotSim(int[] commands, int[][] obstacles) {
        if (commands == null || commands.length == 0) return 0;

        // Pre-process obstacles for O(1) lookup
        Set<String> obstacleSet = new HashSet<>();
        for (int[] obs : obstacles) {
            obstacleSet.add(obs[0] + "$" + obs[1]);
        }

        int x = 0, y = 0, direction = 0, maxDistSq = 0;

        for (int command : commands) {
            if (command == -2) { // Turn Left
                direction = (direction + 3) % 4;
            } else if (command == -1) { // Turn Right
                direction = (direction + 1) % 4;
            } else {
                // Move step-by-step
                for (int i = 0; i < command; i++) {
                    int nextX = x + DIRECTION[direction][0];
                    int nextY = y + DIRECTION[direction][1];

                    if (!obstacleSet.contains(nextX + "$" + nextY)) {
                        x = nextX;
                        y = nextY;
                        maxDistSq = Math.max(maxDistSq, x * x + y * y);
                    } else {
                        break; // Hit an obstacle, stop moving
                    }
                }
            }
        }
        return maxDistSq;
    }
}

Complexity Analysis

Time Complexity (TC): O(N + M * K)

O(N): We iterate through the obstacles array once to populate our HashSet.
O(M*K): We process each of the M commands. For movement commands, we iterate up to K times (where K is the max steps, 9). Since K is a small constant, the simulation scales linearly with the number of commands.

Space Complexity (SC): O(N)

We store N obstacles in a HashSet using Long objects. This is much more memory-efficient than creating String objects for every coordinate and scales only with the number of obstacles.

Mastering Binary Search on Answer: The Book Allocation Problem

Partners DSA — Mon, 06 Apr 2026 19:50:52 +0000

If you've ever prepared for a technical interview at companies like Google, Amazon, or Adobe, you've likely encountered the "Allocate Books" problem. It is a classic challenge that tests your ability to look beyond traditional binary search and apply it to a range of possible answers.

In this post, we’ll break down the problem and walk through an efficient Java solution that uses the Binary Search on Answer technique.

The Problem Statement

You are given an array of integers arr, where arr[i] represents the number of pages in the i^th book. There are k students. The task is to allocate all books to the students such that:

Each student gets at least one book.
Each student is assigned a contiguous sequence of books.
The maximum number of pages assigned to a student is minimized.

Example

Input: arr = [12, 34, 67, 90], k = 2

Output: 113

Explanation: - Option 1: [12] and [34, 67, 90] → Max = 191

Option 2: [12, 34] and [67, 90] → Max = 157
Option 3: [12, 34, 67] and [90] → Max = 113 The smallest possible maximum is 113.

The Intuition: Binary Search on Answer

Usually, we use Binary Search to find an element in a sorted array. Here, we use it to find a value in a range.

1. Defining the Range

Lower Bound (low): The maximum element in the array. Why? Because a student must be able to carry at least the largest book.
Upper Bound (high): The sum of all elements. This is the case where only 1 student is assigned all the books.

2. The Strategy

We pick a "limit" (the middle of our range). We check: "Is it possible to allocate these books so that no student has more than mid pages?"

If Yes, it might be our answer, but we try to find an even smaller maximum (high = mid - 1).
If No, our limit is too small, so we increase it (low = mid + 1).

The Solution (Java)

Here is a clean implementation of the logic:

class Solution {
    public int findPages(int[] arr, int k) {
        // If students are more than books, it's impossible
        if (arr.length < k) {
            return -1;
        }
        return findSmallestPossibleMaximum(arr, k);
    }

    public int findSmallestPossibleMaximum(int[] arr, int k) {
        int low = 0;
        int high = 0;

        // Step 1: Define search space
        for (int num : arr) {
            high += num;
            low = Math.max(low, num);
        }

        int ans = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2; // Avoid potential overflow

            // Step 2: Check feasibility
            if (findNoOfStudents(arr, mid) <= k) {
                ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return ans;
    }

    // Helper function to count students required for a given page limit
    public int findNoOfStudents(int[] arr, int maxPagesAllowed) {
        int student = 1;
        int currentPagesSum = 0;

        for (int i = 0; i < arr.length; i++) {
            if (currentPagesSum + arr[i] > maxPagesAllowed) {
                student++;
                currentPagesSum = arr[i];
            } else {
                currentPagesSum += arr[i];
            }
        }
        return student;
    }
}

Complexity Analysis: Allocate Books

When presenting the Book Allocation problem in an interview or a tutorial, the code is only half the battle. You must be able to explain why the Binary Search on Answer approach is the most efficient.

Time Complexity (TC)

The total time complexity of this solution is:

$O(Nlog(Sum - Max))

Breakdown:

Binary Search Space (O(log(Range))): We are searching for the answer within the range [Max Element, Sum of all Elements]. The number of steps in a binary search is logarithmic relative to the size of the search space.
- Let R = Sum - Max.
- The binary search takes log(R) iterations.
Feasibility Check (O(N)): In every iteration of the binary search, we call the findNoOfStudents (or isPossible) function. This function iterates through the entire array of N books exactly once to determine if the current mid value is a valid page limit.
Total TC: Multiplying the search steps by the work done in each step gives us:

O(Nlog(Sum - Max))

Note: For typical constraints (N = 10^5, Sum = 10^9), log(10^9) is roughly 30. So the total operations are approximately 30 times 10^5, which easily fits within a 1-second time limit.

Space Complexity (SC)

The space complexity of this solution is:

O(1)

Breakdown:

No Auxiliary Data Structures: We do not use any HashMaps, Stacks, or Heaps to solve the problem. We only store a few primitive integer variables (low, high, mid, studentCount, currentPagesSum).
In-Place Processing: We only read from the input array without modifying it or creating a copy.
Iterative Approach: Since we use a while loop for the binary search rather than recursion, there is no extra overhead on the function call stack.