Maximum distance between two 1s in a Binary Array in a given range
Given a binary array of size N and a range in [l, r], the task is to find the maximum distance between two 1s in this given range.
Examples:
Input: arr = {1, 0, 0, 1}, l = 0, r = 3
Output: 3
In the given range from 0 to 3, first 1 lies at index 0 and last at index 3.
Hence, maximum distance = 3 – 0 = 3.Input: arr = {1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0}, l = 3, r = 9
Output: 6
Approach: We will create a segment tree to solve this.
- Each node in the segment tree will have the index of leftmost 1 as well as rightmost 1 and an integer containing the maximum distance between any elements with value 1 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 if it contains at least one 0, or at least one 1.
- If both left and right nodes are valid then:
Let,- l1 = leftmost index of 1 (-1 if 0 doesn’t exist in that interval)
- r1 = rightmost index of 1 (-1 if 0 doesn’t exist in that interval)
- max1 = maximum distance between two 1’s
- Value of max1 in merged node will be maximum of value of max1 in left and right node, and difference between rightmost index of 1 in right node and leftmost index of 1 in left node.
- Value of l1 in merged node will be l1 of left node if it is not -1, else l1 of right node.
- Value of r1 in merged node will be r1 of right node if it is not -1, else r1 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++
// C++ program to find the maximum // distance between two elements // with value 1 within a subarray (l, r) #include <bits/stdc++.h> using namespace std; // Structure for each node // in the segment tree struct node { int l1, r1; int max1; } seg[100001]; // A utility function for // merging two nodes node task(node l, node r) { node x; x.l1 = (l.l1 != -1) ? l.l1 : r.l1; x.r1 = (r.r1 != -1) ? r.r1 : l.r1; x.max1 = max(l.max1, r.max1); if (l.l1 != -1 && r.r1 != -1) x.max1 = max(x.max1, r.r1 - l.l1); 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] == 1) { seg[ind].l1 = seg[ind].r1 = qs; seg[ind].max1 = INT_MIN; } else { seg[ind].l1 = seg[ind].r1 = -1; seg[ind].max1 = 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 a range qs to qe node query( int qs, int qe, int ns, int ne, int ind) { node x; x.l1 = x.r1 = -1; x.max1 = 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]); int l = 3, r = 9; // Build the segment tree build(0, n - 1, 1, arr); // Query in range 3 to 9 node ans = query(l, r, 0, n - 1, 1); cout << ans.max1 << "\n" ; return 0; } |
Java
// Java program to find the maximum // distance between two elements // with value 1 within a subarray (l, r) import java.util.*; class GFG{ // Structure for each node // in the segment tree static class node { int l1, r1; int max1; } static node []seg = new node[ 100001 ]; // A utility function for // merging two nodes static node task(node l, node r) { node x = new node(); x.l1 = (l.l1 != - 1 ) ? l.l1 : r.l1; x.r1 = (r.r1 != - 1 ) ? r.r1 : l.r1; x.max1 = Math.max(l.max1, r.max1); if (l.l1 != - 1 && r.r1 != - 1 ) x.max1 = Math.max(x.max1, r.r1 - l.l1); return x; } // A recursive function that constructs // Segment Tree for given String static 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] == 1 ) { seg[ind].l1 = seg[ind].r1 = qs; seg[ind].max1 = Integer.MIN_VALUE; } else { seg[ind].l1 = seg[ind].r1 = - 1 ; seg[ind].max1 = Integer.MIN_VALUE; } 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 a range qs to qe static node query( int qs, int qe, int ns, int ne, int ind) { node x = new node(); x.l1 = x.r1 = - 1 ; x.max1 = Integer.MIN_VALUE; // 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 public static void main(String[] args) { for ( int i= 0 ; i < 100001 ; i++) seg[i] = new node(); int arr[] = { 1 , 1 , 0 , 1 , 0 , 1 , 0 , 1 , 0 , 1 , 0 , 1 , 1 , 0 }; int n = arr.length; int l = 3 , r = 9 ; // Build the segment tree build( 0 , n - 1 , 1 , arr); // Query in range 3 to 9 node ans = query(l, r, 0 , n - 1 , 1 ); System.out.print(ans.max1+ "\n" ); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 program to find the maximum # distance between two elements # with value 1 within a subarray (l, r) import sys # Structure for each node # in the segment tree class node(): def __init__( self ): self .l1 = 0 self .r1 = 0 self .max1 = 0 seg = [node() for i in range ( 100001 )] # A utility function for # merging two nodes def task(l, r): x = node() x.l1 = l.l1 if (l.l1 ! = - 1 ) else r.l1 x.r1 = r.r1 if (r.r1 ! = - 1 ) else l.r1 x.max1 = max (l.max1, r.max1) # If both the nodes are valid if (l.r1 ! = - 1 and r.l1 ! = - 1 ): x.max1 = max (x.max1, r.r1 - l.l1) return x # A recursive function that constructs # Segment Tree for given string def build(qs, qe, ind, arr): # If start is equal to end then # insert the array element if (qs = = qe): if (arr[qs] = = 1 ): seg[ind].l1 = seg[ind].r1 = qs seg[ind].max1 = - sys.maxsize else : seg[ind].l1 = seg[ind].r1 = - 1 seg[ind].max1 = - sys.maxsize return 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 a range qs to qe def query(qs, qe, ns, ne, ind): x = node() x.l1 = x.r1 = - 1 x.max1 = - sys.maxsize # If the range lies in this segment if (qs < = ns and qe > = ne): return seg[ind] # If the range is out of the bounds # of this segment if (ne < qs or ns > qe or ns > ne): return x # Else query for the right and left # child node of this subtree # and merge them mid = (ns + ne) >> 1 l = query(qs, qe, ns, mid, ind << 1 ) r = query(qs, qe, mid + 1 , ne, ind << 1 | 1 ) x = task(l, r) return x # Driver code if __name__ = = "__main__" : arr = [ 1 , 1 , 0 , 1 , 0 , 1 , 0 , 1 , 0 , 1 , 0 , 1 , 1 , 0 ] n = len (arr) l = 3 r = 9 # Build the segment tree build( 0 , n - 1 , 1 , arr) # Query in range 3 to 9 ans = query(l, r, 0 , n - 1 , 1 ) print (ans.max1) # This code is contributed by rutvik_56 |
C#
// C# program to find the maximum // distance between two elements // with value 1 within a subarray (l, r) using System; class GFG{ // Structure for each node // in the segment tree class node { public int l1, r1; public int max1; } static node []seg = new node[100001]; // A utility function for // merging two nodes static node task(node l, node r) { node x = new node(); x.l1 = (l.l1 != -1) ? l.l1 : r.l1; x.r1 = (r.r1 != -1) ? r.r1 : l.r1; x.max1 = Math.Max(l.max1, r.max1); if (l.l1 != -1 && r.r1 != -1) x.max1 = Math.Max(x.max1, r.r1 - l.l1); return x; } // A recursive function that constructs // Segment Tree for given String static 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] == 1) { seg[ind].l1 = seg[ind].r1 = qs; seg[ind].max1 = int .MinValue; } else { seg[ind].l1 = seg[ind].r1 = -1; seg[ind].max1 = int .MinValue; } 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 a range qs to qe static node query( int qs, int qe, int ns, int ne, int ind) { node x = new node(); x.l1 = x.r1 = -1; x.max1 = int .MinValue; // 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 public static void Main(String[] args) { for ( int i = 0; i < 100001; i++) seg[i] = new node(); int []arr = { 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0 }; int n = arr.Length; int l = 3, r = 9; // Build the segment tree build(0, n - 1, 1, arr); // Query in range 3 to 9 node ans = query(l, r, 0, n - 1, 1); Console.Write(ans.max1+ "\n" ); } } // This code is contributed by Princi Singh |
Javascript
<script> // JavaScript program to find the maximum // distance between two elements // with value 1 within a subarray (l, r) // Structure for each node // in the segment tree class node { constructor() { this .l1 = 0; this .r1 = 0; this .max1 =0; } } var seg = Array(100001); // A utility function for // merging two nodes function task(l, r) { var x = new node(); x.l1 = (l.l1 != -1) ? l.l1 : r.l1; x.r1 = (r.r1 != -1) ? r.r1 : l.r1; x.max1 = Math.max(l.max1, r.max1); if (l.l1 != -1 && r.r1 != -1) x.max1 = Math.max(x.max1, r.r1 - l.l1); return x; } // A recursive function that constructs // Segment Tree for given String function build(qs, qe, ind, arr) { // If start is equal to end then // insert the array element if (qs == qe) { if (arr[qs] == 1) { seg[ind].l1 = seg[ind].r1 = qs; seg[ind].max1 = -1000000000; } else { seg[ind].l1 = seg[ind].r1 = -1; seg[ind].max1 = -1000000000; } return ; } var 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 a range qs to qe function query(qs, qe, ns, ne, ind) { var x = new node(); x.l1 = x.r1 = -1; x.max1 = -1000000000; // 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 var mid = (ns + ne) >> 1; var l = query(qs, qe, ns, mid, ind << 1); var r = query(qs, qe, mid + 1, ne, ind << 1 | 1); x = task(l, r); return x; } // Driver code for ( var i = 0; i < 100001; i++) seg[i] = new node(); var arr = [1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0]; var n = arr.length; var l = 3, r = 9; // Build the segment tree build(0, n - 1, 1, arr); // Query in range 3 to 9 var ans = query(l, r, 0, n - 1, 1); document.write(ans.max1+ "<br>" ); </script> |
Output:
6
Contact Us