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

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.

Solution Approach 

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 = 2⁰ + 2¹ + 2² + … + 2^H. Sum of this geometric series = 2^(H+1) - 1 = 2 * 2^H - 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.