1.
Introduction
1.1.
Example
1.1.1.
Input
1.1.2.
Output
1.1.3.
Explanation
1.2.
Solution Approach
1.3.
Naive Solution
1.3.1.
Idea and Algorithm
1.3.2.
C++ Code implementation
1.3.3.
Output
1.3.4.
Complexity Analysis
1.4.
Efficient Solution
1.4.1.
Idea and Algorithm
1.4.2.
Building the tree recursively - O(N)
1.4.3.
Updating the tree recursively - O(logN)
1.4.4.
C++ Code implementation
1.4.5.
Complexity Analysis
2.
FAQs
3.
Key Takeaways
Last Updated: Mar 27, 2024

# Query to find the length of the longest subarray consisting of only 1s

Ayush Prakash

## Introduction

The problem statement: Given an integer array 'input' of length 'n' consisting of either 1 or 0. Also, given a 2D' queries' array, which contain two types of queries,

1. {1}, Print the length of the longest subarray consisting of only 1s.
2. {2, pos}, flip the number in the input array at index = 'pos'. That is, change 1 to 0 and vice versa.

We need to perform these operations (queries) efficiently.

### Example

#### Input

``````input = {0, 1, 1, 0, 0, 1, 1, 0, 1, 1}
queries = {{1}, {2, 7}, {1}}``````

#### Output

``````2
5``````

#### Explanation

The first query is of type(a). We need to print the longest subarray consisting of only 1s. As it is clear from the input, the answer is 2.

The second query is of type(b). We have to update the input[7] = 1 (since it is 0 currently)

The third query is again of type(a). We print the largest subarray consisting of 1s which is 7. Because after the update in the previous query, the value of input[7] = 1.

### Naive Solution

#### Idea and Algorithm

Implement the queries in a brute force way.

For update queries (type(b)), just flip the value at input[i]. If the current value is 1 make it 0 and vice versa.

For type(a) queries, we need to tell the longest subarray with only 1s. We simply traverse the array starting from i  = 0 until n - 1. We maintain a count variable ‘cnt’ that is incremented by 1 when ‘1’ is encountered. So essentially, ‘cnt’ stores the length of consecutive 1s (at that point of time). On the other hand, if ‘0’ is encountered, we reset the value of ‘cnt’ to 0. This signifies that there is a break in the continuity of 1s. Also, we maintain a variable ‘maxCount’ which is updated every time cnt is incremented. It is updated as max(cnt, maxCnt). This stores the length of the longest subarray consisting of only 1s and this is our final answer.

#### C++ Code implementation

``````#include <bits/stdc++.h>

using namespace std;

// Calculating the value of the longest subarray with only 1s
int longestSubarrWithAll1s(vector<int> &input)
{
int maxCnt = 0;
int cnt = 0;
for (int i = 0; i < input.size(); i++)
{

/*
Incrementing the value of cnt, and also
updating the value of maxCnt when a 1 is
encountered
*/
if (input[i] == 1)
{
cnt += 1;
maxCnt = max(maxCnt, cnt);
}

// Resetting the value of cnt, when a 0 is encountered
else
{
cnt = 0;
}
}
return maxCnt;
}

int main()
{
vector<int> input{0, 1, 1, 0, 0, 1, 1, 0, 1, 1};
vector<vector<int>> queries{{1}, {2, 7}, {1}};
for (vector<int> query : queries)
{

// For query of type(a)
if (query.size() == 1)
{
cout << longestSubarrWithAll1s(input) << endl;
}

// For query of type(b)
else
{
// Flipping the value at input[query[1]]
input[query[1]] ^= 1;
}
}
}``````

#### Output

``````2
5``````

#### Complexity Analysis

Time complexity: O(Q * N)

Q is the number of queries, and N is the size of the input array. For type(a) query, the time taken is O(N) since we have to traverse the whole input array to find the length of the longest subarray consisting of only 1s. For type(b) query, we need to flip the value at the given position. So it is a constant-time operation. So for Q queries, the overall time complexity becomes

O(Q * N).

Space complexity: O(1)

We are not using any extra space.

### Efficient Solution

#### Idea and Algorithm

The idea is to use segment trees to achieve a better time complexity. The height of a segment tree is ceil(logN). A segment tree allow us to query/update in O(logN) in general. Hence, segment trees is a decent choice because our question demands for those kind of operations. To know more about segment trees please follow the link. Hence, we build three-segment trees, 'maxT', 'preT' and 'sufT' in order to solve the problem efficiently. After reading the article, you will know why we used three different segment trees and not one.

maxT[idx]: stores the length of the longest subarray consisting of only 1s for some range

[low, hig]. For example, maxT[0] stores the longest subarray consisting of only 1s in the whole array i.e. low = 0 and high = n - 1.

preT[idx]: stores the length of the longest subarray consisting of only 1s starting at 'low'.

sufT[idx]: stores the length of the longest subarray consisting of only 1s ending at 'high'.

In the above image, we have an arbitrary node in the segment tree pointed by ‘idx’ which corresponds to the subarray that ranges from low to high we have:

• maxT[idx] = 5,
• perT[idx] = 2,
• sufT[idx] = 0.

#### Building the tree recursively - O(N)

The pointers to the nodes in the segment trees and what range they correspond to and the parent-child relationship is described below:

• idx: [low, high]
• leftIdx = 2*idx + 1: [low, mid] (left-child)
• rightIdx = 2*idx + 2: [mid + 1, high] (right-child)

here, mid = (low + high) / 2

We build the tree from bottom to top. That is, we derive the value of the parent node based on the child nodes. We use the following relations to obtain the values in the segment trees.

``maxT[idx] = max(max(maxT[leftIdx], maxT[rightIdx]), preT[rightIdx] + sufT[leftIdx]);``

Here, we have 3 possible values maxT[leftIdx], maxT[rightIdx] and preT[rightIdx] + sufT[leftIdx]. We have to take the maximum of the three. The longest subarray exists in the left half or the right half, or if we get a new longest subarray upon concatenating the two halves.

We calculate preT[idx] as:

``preT[idx] = preT[leftIdx] == mid - low + 1 ? preT[leftIdx] + preT[rightIdx] : preT[leftIdx]``

Here, if the left half of the subarray contains all 1s, then preT[i] = preT[leftIdx] + preT[rightIdx] else it is simple preT[leftIdx].

and sufT[idx] as:

``sufT[idx] = sufT[rightIdx] == high - mid ? sufT[leftIdx] + sufT[rightIdx] : sufT[rightIdx];``

Here, if the right half of the subarray contains all 1s, then suf[idx] = sufT[rightIdx] + sufT[leftIdx], else it is simply, sufT[rightIdx].

#### Updating the tree recursively - O(logN)

For the update queries, we go down the tree to make a point update, i.e. flip the value at 'pos' and propagate the change upwards until the root. We use the same relations for propagating the change.

#### C++ Code implementation

``````#include <algorithm>
using namespace std;

// Declaring globals
vector<int> maxT;
vector<int> preT;
vector<int> sufT;

void build(vector<int> &input, int idx, int low, int high)
{

//Base case, when we reach a leaf node,
if (low == high)
{
preT[idx] = input[low];
sufT[idx] = input[low];
maxT[idx] = input[low];
return;
}

int mid = low + (high - low) / 2;
int leftIdx = 2 * idx + 1, rightIdx = 2 * idx + 2;

// Recursively build the left and right subtree
build(input, leftIdx, low, mid);
build(input, rightIdx, mid + 1, high);

// Derive the value of the parent using the child's value
preT[idx] = preT[leftIdx] == mid - low + 1 ? preT[leftIdx] + preT[rightIdx] : preT[leftIdx];
sufT[idx] = sufT[rightIdx] == high - mid ? sufT[leftIdx] + sufT[rightIdx] : sufT[rightIdx];
maxT[idx] = max(max(maxT[leftIdx], maxT[rightIdx]), preT[rightIdx] + sufT[leftIdx]);
return;
}

void update(int pos, int low, int high, int idx, vector<int> &input)
{

// if pos lie outside the range of the node
if (high < pos or low > pos)
{
return;
}

// Base case, when we reach a leaf node
if (low == high)
{
preT[idx] = input[pos];
sufT[idx] = input[pos];
maxT[idx] = input[pos];
}
else
{
int mid = low + (high - low) / 2;
int leftIdx = 2 * idx + 1, rightIdx = 2 * idx + 2;

// Update the left and right subtrees recursively
update(pos, low, mid, leftIdx, input);
update(pos, mid + 1, high, rightIdx, input);

// The value of the parent is derived from the value of its children
preT[idx] = preT[leftIdx] == mid - low + 1 ? preT[leftIdx] + preT[rightIdx] : preT[leftIdx];
sufT[idx] = sufT[rightIdx] == high - mid ? sufT[leftIdx] + sufT[rightIdx] : sufT[rightIdx];
maxT[idx] = max(max(maxT[leftIdx], maxT[rightIdx]), preT[rightIdx] + sufT[leftIdx]);
}
}

int main()
{

// Initialising input, maxT, preT, sufT
vector<int> input{0, 1, 1, 0, 0, 1, 1, 0, 1, 1};
int n = input.size();
maxT.resize(4 * n, 0);
preT.resize(4 * n, 0);
sufT.resize(4 * n, 0);

// Building the trees
build(input, 0, 0, n - 1);

// Initialising the queries
vector<vector<int>> queries{{1}, {2, 7}, {1}};

// Iterating over the queries
for (vector<int> q : queries)
{

/*
maxT[0] stores the length of the longest subarray
consisting of only 1s in the range [0, n-1], for query type(a)
*/
if (q.size() == 1)
{
cout << maxT[0] << endl;
}

// here we do the update operation, for query type(b)
else
{
int pos = q[1];
input[pos] ^= 1;
update(pos, 0, n - 1, 0, input);
}
}
}``````

Output

``````2
5``````

#### Complexity Analysis

Time complexity: O(QlogN)

For type(a) queries, we print the root node's value in the maxT tree. This is a constant-time operation.

For type(b) queries, we need to update the input array's value and make relevant changes in the segment trees. We need to gown down the tree, make a point update, and propagate that change until the root. The tree's height is logN, hence the time taken for this operation is O(logN).

The overall time complexity becomes O(QlogN) for 'Q' number of queries.

Space complexity: O(N)

We are building three segment trees(maxT, preT and sufT), each of size 4*n. Therefore, the overall space complexity is O(N).

## FAQs

1. For an input array of size 'n' we define the size of the segment tree as 4 * n. Explain.
An important observation is the height of a segment tree H = ceil(logn). Total number of nodes = 20 + 21 + 22 + … + 2H. Sum of this geometric series = 2(H+1) - 1 = 2 * 2H - 1.
H = ceil(logn) can be approximated to logn + 1 to ease the calculation. Hence the total number of nodes = 2 * 2(logn + 1) - 1 = 2 * 2 * 2(logn) - 1 = 4*n - 1 ~ 4*n

2. Is a segment tree a complete tree or a full tree?
The segment tree is a full binary tree as we always divide segments of the given array into halves at every level.

## Key Takeaways

In this blog, we discussed a really interesting problem: Query to find the length of the longest subarray consisting of only 1s. We learned two approaches, first, the naive one. It is easy to come up with. The time complexity for querying in this case = O(n) and updation = O(1). For Q queries, we could easily get a time limit error.

So we used segment trees to optimize the solution. The time complexity for querying and updation = O(logn). So, now we could easily pass all our test cases. But this optimization in time complexity cost us O(n) extra space.

Questions based on segment trees are very popular in competitive programming. To ace competitive programming, you can follow the best cp course online.

If you love solving coding problems, you can check this amazing platform Coding Ninjas Studio. Happy coding!!

Live masterclass