Maximum distance between two elements with value 0 in a subarray

Given a binary array consisting of only 0s and 1s, find the maximum distance between two elements with value 0 in a subarray {l,r}.

Examples:

Input : arr = {1,0,0,1}, l=0, r=3
Output : 1
Clearly, in the range from 0 to 3, first 0 lies at index 1 and last at index 2.
Hence, the distance 2-1 =1.

Input : arr = {1,1,0,1,0,1,0,1,0,1,0,1,1,0}, l=3, r=9
Output : 4

Pre-requisite: Segment Trees

Approach:

We will create a segment tree to solve this. Each node in the segment tree will have the index of leftmost 0 as well as rightmost 0 and an integer containing the maximum distance between any elements with value 0 in a subarray {l,r}.
Now, in this segment tree we can merge left and right nodes as below:
- If left node is not valid, return right node.
- If right node is not valid, return left node.
- A node is valid iff it contains at least one 0, or at least one 1.
- If both left and right nodes are valid then:
  Let,
  - l0 = leftmost index of 0 (-1 if 0 doesn’t exist in that interval)
  - r0 = rightmost index of 0 (-1 if 0 doesn’t exist in that interval)
  - max0 = maximum distance between two 0’s
  - Value of max0 in merged node will be maximum of maximum of value of max0 in left and right node, and difference between rightmost index of 0 in right node and leftmost index of 0 in left node.
  - Value of l0 in merged node will be l0 of left node if it is not -1, else l0 of right node.
  - Value of r0 in merged node will be r0 of right node if it is not -1, else r0 of left node.
Then, finally to find the answer we just need to call query function for the given range {l,r}.

Below is the implementation of the above approach:

// C++ program to find the maximum
// distance between two elements
// with value 0 within a subarray (l,r)
#include <bits/stdc++.h>

using namespace std;

// Structure for each node
// in the segment tree
struct node {
  int l0, r0;
  int max0;
}
seg[100001];


// A utility function for
// merging two nodes
node task(node l, node r) {
  node x;
  x.l0 = (l.l0 != -1) ? l.l0 : r.l0;
  x.r0 = (r.r0 != -1) ? r.r0 : l.r0;
  x.max0 = max(l.max0, r.max0);
  
  if (l.l0 != -1 && r.r0 != -1)
    x.max0 = max(x.max0, r.r0 - l.l0);
  return x;
}

// A recursive function that constructs
// Segment Tree for given string
void build(int qs, int qe, int ind, int arr[]) {
  // If start is equal to end then
  // insert the array element
  if (qs == qe) {
    if (arr[qs] == 0) {
      seg[ind].l0 = seg[ind].r0 = qs;
      seg[ind].max0 = INT_MIN;
    } else {
      seg[ind].l0 = seg[ind].r0 = -1;
      seg[ind].max0 = INT_MIN;
    }
    return;
  }
  int mid = (qs + qe) >> 1;
  // Build the segment tree
  //for range qs to mid
  build(qs, mid, ind << 1, arr);
  // Build the segment tree
  //for range mid+1 to qe
  build(mid + 1, qe, ind << 1 | 1, arr);
  // merge the two child nodes
  //to obtain the parent node
  seg[ind] = task(seg[ind << 1], seg[ind << 1 | 1]);
}
// Query in an range qs to qe
node query(int qs, int qe, int ns, int ne, int ind) {
  node x;
  x.l0 = x.r0 = -1;
  x.max0 = INT_MIN;
  // If the range lies in this segment
  if (qs <= ns && qe >= ne)
    return seg[ind];
  // If the range is out of the bounds
  // of this segment
  if (ne < qs || ns > qe || ns > ne)
    return x;
  // Else query for the right and left
  // child node of this subtree
  // and merge them
  int mid = (ns + ne) >> 1;
  node l = query(qs, qe, ns, mid, ind << 1);
  node r = query(qs, qe, mid + 1, ne, ind << 1 | 1);
  x = task(l, r);
  return x;
}
// Driver code
int main() {
  int arr[] = {1,1,0,1,0,1,0,1,0,1,0,1,1,0};
  int n = sizeof(arr) / sizeof(arr[0]);
  
  // Build the segment tree
  build(0, n - 1, 1, arr);
  
  // Query in range 3 to 9
  node ans = query(3, 9, 0, n - 1, 1);
  cout << ans.max0 << "\n";
  
  return 0;
}

Output:

Time complexity is O(N)
Space complexity is O(N)