Day 5 of 60 Days of DSA — Flipping Bits & Merging Intervals

Two powerful interval-based problems that test your ability to reason about subarrays and ranges — both of which are frequent in…

Day 5 of 60 Days of DSA — Flipping Bits & Merging Intervals

Two powerful interval-based problems that test your ability to reason about subarrays and ranges — both of which are frequent in interviews.

Welcome back to Day 5 of 60 Days of DSA 🚀

By the end of this article, you’ll be confident about:

Finding the best subarray to maximize 1s in a binary string using a modified Kadane’s algorithm
Efficiently inserting and merging intervals while maintaining order
Handling overlapping range logic — a concept used in many advanced DSA and system design problems

Let’s dive right in 👇

Problem 1: Flip — Maximize Number of 1s

Problem Description

You are given a binary string A(i.e., with characters 0 and 1) consisting of characters A1, A2, …, AN. In a single operation, you can choose two indices, L and R, such that 1 ≤ L ≤ R ≤ N and flip the characters AL, AL+1, …, AR. By flipping, we mean changing character 0 to 1 and vice-versa.

Your aim is to perform ATMOST one operation such that in the final string number of 1s is maximized.

If you don’t want to perform the operation, return an empty array. Else, return an array consisting of two elements denoting L and R. If there are multiple solutions, return the lexicographically smallest pair of L and R.

NOTE: Pair (a, b) is lexicographically smaller than pair (c, d) if a < c or, if a == c and b < d.

Problem Constraints

1 <= size of string <= 100000

Input Format

First and only argument is a string A.

Output Format

Return an array of integers denoting the answer.

Example Input

Input 1:

A = "010"

Input 2:

A = "111"

Example Output

Output 1:

[1, 1]

Output 2:

[]

Example Explanation

Explanation 1:

A = "010"

Pair of [L, R] | Final string
_______________|_____________
[1 1] | "110"
[1 2] | "100"
[1 3] | "101"
[2 2] | "000"
[2 3] | "001"

We see that two pairs [1, 1] and [1, 3] give same number of 1s in final string. So, we return [1, 1].

Explanation 2:

No operation can give us more than three 1s in final string. So, we return empty array [].

Solution Approach

When you flip bits:

Each 0 → 1 increases total 1s by +1
Each 1 → 0 decreases total 1s by -1

So the task is equivalent to finding a subarray where
👉 (Number of 0s − Number of 1s) is maximum.

In other words, it’s like finding the maximum subarray sum,
If we treat 0 as +1 and 1 as −1.

This is a direct application of Kadane’s Algorithm! ⚡

Solution Code

Solution 1:

Normally, solving it by finding out the difference

function flip(A){
// to convert A to Array from string
 A = Array.from(A).map(el => Number(el));
 let left = 0;
 let finalOp = new Array(2);
 let maxZeros = 0;
 let zeroes = 0, ones = 0;
 for(let i=0 ; i< A.length; i++){
 A[i] == 1? ones++: zeroes++;
 let diff = zeroes-ones;
 if(diff < 0){
 ones = 0;
 zeroes = 0;
 left = i+1;
 }
 if(maxZeros < diff){
 maxZeros = diff;
 finalOp[0] = left+1;
 finalOp[1] = i+1;
 }
 }
 return finalOp[0] ? finalOp: [];
}

Solution 2:

By Kadane’s Algorithm 0->1 and 1->-1

function flip(A){
 // Using kadane's algorithm 0->1 amd 1-> -1 
 // problem becomes equal to maximum subarray sum
 A = Array.from(A).map(el => Number(el));
 for(let i=0; i< A.length ; i++){
 if(A[i] == 1){
 A[i] = -1;
 }else{
 A[i] = 1
 }
 }
 let max = 0;
 let left = 0;
 let sum =0;
 let op = new Array(2);
 for(let i=0;i <A.length; i++)
 {
 sum += A[i];
 if(sum > max){
 max = sum;
 op[0] = left+1;
 op[1] = i+1;
 }
 if(sum < 0){
 sum = 0;
 left = i+1;
 }
 
 }
 return max ==0? []: op;
}

Complexity

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

Key Takeaways

✅ Convert logical problems into mathematical differences
✅ Kadane’s algorithm is one of the most powerful subarray tools
✅ Always consider lexicographical order in tie-breaking

Problem 2: Insert Interval

Problem Description

You have a set of non-overlapping intervals. You are given a new interval [start, end]. Insert this new interval into the set of intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Problem Constraints

0 <= |intervals| <= 105

Input Format

First argument is the vector of intervals

second argument is the new interval to be merged

Output Format

Return the vector of intervals after merging

Example Input

Input 1:

Given intervals [1, 3], [6, 9] insert and merge [2, 5] .

Input 2:

Given intervals [1, 3], [6, 9] insert and merge [2, 6] .

Example Output

Output 1:

[ [1, 5], [6, 9] ]

Output 2:

[ [1, 9] ]

Example Explanation

Explanation 1:

(2,5) does not completely merge the given intervals

Explanation 2:

(2,6) completely merges the given intervals

Solution Approach

There are three possible cases when comparing intervals:

let’s suppose [a1, b1], [a2,b2] are the two intervals

Solution

function mergeIntervals(A, B){
 let sortedList = []
 let a1 = B[0];
 let b1 = B[1];

 for(let i=0; i<A.length; i++){
 let a2 = A[i][0];
 let b2 = A[i][1];
 if(b1 >= a2){
 if(a1 > b2){
 sortedList.push([a2, b2]);
 }else{
 a1 = a1 > a2 ? a2: a1;
 b1 = b1 > b2 ? b1: b2;
 }
 }else{
 sortedList.push([a1,b1]);
 a1 = a2;
 b1 = b2;
 }
 }
 sortedList.push([a1, b1]);
 return sortedList;
}

⏱️ Complexity

Time: O(N)
Space: O(N) (in worst case)

🧭 Key Takeaways

✅ Carefully handle overlapping logic using min/max
✅ Maintaining order is crucial for merging
✅ Visualising intervals on a number line helps build intuition

Quick Quiz

1️⃣ In the Flip problem, if the string is "111", what should be returned?
a) [1,3]
b) [1,1]
c) []

2️⃣ For the Insert Interval problem, if you insert [2,6] into [[1,3],[6,9]], what’s the result?
a) [[1,6],[9,9]]
b) [[1,9]]
c) [[1,3],[2,6],[6,9]]

That’s it for Day 5🎯
You just mastered Kadane’s variation and Interval merging, both extremely common in interviews like Amazon, Google, and Adobe.

Day 5 of 60 Days of DSA — Flipping Bits & Merging Intervals