Given a binary array arr[] of size n and a value k. The task is to find the length of the longest subarray having difference in the count of 1’s and 0’s equal to k. The count of 1’s should be equal to or greater than the count of 0’s in the subarray according to the value of k.
Examples:
Input: arr[] = {0, 1, 1, 0, 1}, k = 2
Output: 4
The highlighted portion is the required subarray
{0, 1, 1, 0, 1}. In the subarray count of 1's is 3
and count of 0's is 1.
Therefore, difference in count = 3 - 1 = 2.
Input: arr[] = {1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1}, k = 0
Output: 6
The highlighted portion is the required subarray
{1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1}. In the subarray
count of 1's is 3 and count of 0's is 3.
Therefore, difference in count = 3 - 3 = 0.
Naive Approach: Consider the difference in the count of 1’s and 0’s of all the sub-arrays and return the length of the longest sub-array having required difference equal to ‘k’. Time Complexity will be O(n^2).
Efficient Approach: This problem is a variation of finding the longest sub-array having sum k. Replace all the 0’s in the arr[] with -1 and then find the longest subarray of ‘arr’ having sum equal to ‘k’.
Implementation:
C++
// C++ implementation of above approach#include <bits/stdc++.h>using namespace std;// function to find the length of the longest// subarray having difference in the count// of 1's and 0's equal to kint lenOfLongSubarr(int arr[], int n, int k){ // unordered_map 'um' implemented // as hash table unordered_map<int, int> um; int sum = 0, maxLen = 0; // traverse the given array for (int i = 0; i < n; i++) { // accumulate sum sum += ((arr[i] == 0) ? -1 : arr[i]); // when subarray starts from index '0' if (sum == k) maxLen = i + 1; // make an entry for 'sum' if it is // not present in 'um' if (um.find(sum) == um.end()) um[sum] = i; // check if 'sum-k' is present in 'um' // or not if (um.find(sum - k) != um.end()) { // update maxLength if (maxLen < (i - um[sum - k])) maxLen = i - um[sum - k]; } } // required maximum length return maxLen;}// Driver Codeint main(){ int arr[] = { 0, 1, 1, 0, 1 }; int n = sizeof(arr) / sizeof(arr[0]); int k = 2; cout << "Length = " << lenOfLongSubarr(arr, n, k); return 0;} |
Java
// Java implementation of the above approach.import java.util.HashMap;import java.util.Map;class GfG{ // Function to find the length of the longest // subarray having difference in the count // of 1's and 0's equal to k static int lenOfLongSubarr(int arr[], int n, int k) { // unordered_map 'um' implemented // as hash table HashMap<Integer, Integer> um = new HashMap<>(); int sum = 0, maxLen = 0; // traverse the given array for (int i = 0; i < n; i++) { // accumulate sum sum += ((arr[i] == 0) ? -1 : arr[i]); // when subarray starts from index '0' if (sum == k) maxLen = i + 1; // make an entry for 'sum' if // it is not present in 'um' if (!um.containsKey(sum)) um.put(sum, i); // check if 'sum-k' is present // in 'um' or not if (um.containsKey(sum - k)) { // update maxLength if (maxLen < (i - um.get(sum - k))) maxLen = i - um.get(sum - k); } } // required maximum length return maxLen; } // Driver code public static void main(String []args) { int arr[] = { 0, 1, 1, 0, 1 }; int n = arr.length; int k = 2; System.out.println("Length = " + lenOfLongSubarr(arr, n, k)); }}// This code is contributed by Rituraj Jain |
Python
# Python3 implementation of above approach# function to find the length of the longest# subarray having difference in the count# of 1's and 0's equal to kdef lenOfLongSubarr(arr, n, k): # unordered_map 'um' implemented # as hash table um = dict() Sum, maxLen = 0, 0 # traverse the given array for i in range(n): # accumulate sum if arr[i] == 0: Sum += -1 else: Sum+=arr[i] # when subarray starts from index '0' if (Sum == k): maxLen = i + 1 # make an entry for 'Sum' if it is # not present in 'um' if (Sum not in um.keys()): um[Sum] = i # check if 'Sum-k' is present in 'um' # or not if ((Sum - k) in um.keys()): # update maxLength if (maxLen < (i - um[Sum - k])): maxLen = i - um[Sum - k] # required maximum length return maxLen# Driver Codearr = [0, 1, 1, 0, 1]n = len(arr)k = 2print("Length = ",lenOfLongSubarr(arr, n, k))# This code is contributed by mohit kumar |
C#
// C# implementation of the approachusing System;using System.Collections.Generic;class GFG{ // Function to find the length of the longest // subarray having difference in the count // of 1's and 0's equal to k static int lenOfLongSubarr(int []arr, int n, int k) { // unordered_map 'um' implemented // as hash table Dictionary<int, int> um = new Dictionary<int, int>(); int sum = 0, maxLen = 0; // traverse the given array for (int i = 0; i < n; i++) { // accumulate sum sum += ((arr[i] == 0) ? -1 : arr[i]); // when subarray starts from index '0' if (sum == k) maxLen = i + 1; // make an entry for 'sum' if // it is not present in 'um' if (!um.ContainsKey(sum)) um.Add(sum, i); // check if 'sum-k' is present // in 'um' or not if (um.ContainsKey(sum - k)) { // update maxLength if (maxLen < (i - um[sum - k])) maxLen = i - um[sum - k]; } } // required maximum length return maxLen; } // Driver code public static void Main(String []args) { int []arr = { 0, 1, 1, 0, 1 }; int n = arr.Length; int k = 2; Console.WriteLine("Length = " + lenOfLongSubarr(arr, n, k)); }}// This code is contributed by Princi Singh |
Javascript
<script>// Javascript implementation of above approach// function to find the length of the longest// subarray having difference in the count// of 1's and 0's equal to kfunction lenOfLongSubarr(arr, n, k){ // unordered_map 'um' implemented // as hash table var um = new Map(); var sum = 0, maxLen = 0; // traverse the given array for (var i = 0; i < n; i++) { // accumulate sum sum += ((arr[i] == 0) ? -1 : arr[i]); // when subarray starts from index '0' if (sum == k) maxLen = i + 1; // make an entry for 'sum' if it is // not present in 'um' if (!um.has(sum)) um.set(sum, i); // check if 'sum-k' is present in 'um' // or not if (um.has(sum - k)) { // update maxLength if (maxLen < (i - um.get(sum-k))) maxLen = i - um.get(sum-k); } } // required maximum length return maxLen;}// Driver Codevar arr = [0, 1, 1, 0, 1];var n = arr.length;var k = 2;document.write( "Length = " + lenOfLongSubarr(arr, n, k));// This code is contributed by rrrtnx.</script> |
Output
Length = 4
Complexity Analysis:
- Time Complexity: O(n)
- Auxiliary Space: O(n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
