Subarrays

Question 1

(Medium) Contiguous Array

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.

Example 1:

Input: [0,1]

Output: 2

Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.

Answer 1

Approach:

Standard Subarray problem.

Prefix cummulative sum & hashmap to maintain prefixes first occurance along with index.

public int findMaxLength(int[] nums) {
HashMap< Integer,Integer> prefixIdMap = new HashMap< Integer,Integer>();

int prefix=0;
int res=0;
for(int i=0;i< nums.length;i++){
if(nums[i]==0) prefix–;
else prefix++;
if(prefix==0) res=i+1;
if(prefixIdMap.containsKey(prefix)){
res=Math.max(res,i-prefixIdMap.get(prefix));
}
if(!prefixIdMap.containsKey(prefix)){
prefixIdMap.put(prefix, i);
}
}
return res;
}

Question 2

(Medium) Subarray Sum Equals K

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals k.

Example 1:

Input:nums = [1,1,1], k = 2

Output: 2

Answer 2

Approach:

Use cumulative prefix sum along with hashmap to track prefixes that occurred along with the count of occurrences.

public int subarraySum(int[] nums, int k) {

 HashMap\< Integer,Integer\> prefixIdMap = new HashMap\< Integer, Integer\>();
 int prefix=0;
 int res=0;
 prefixIdMap.put(0,1);
 for(int i=0;i\< nums.length;i++){
 prefix+=nums[i]; 
 //For every i, we check the number of times prefix-k has occured already, since it will determine the number of times a subarray with sum k which ends at the current index occured. We increment the count by this.
//Since if an index a (a\< b) has sum of prefix-k and if b has sum of prefix. Then the subarray [a+1,b] will have a sum of k.

if(prefixIdMap.containsKey(prefix-k))
res+=prefixIdMap.get(prefix-k);
prefixIdMap.put(prefix, prefixIdMap.getOrDefault(prefix, 0) + 1);
}
return res;
}

Question 3

(Medium) Longest Well-Performing Interval

We are given hours, a list of the number of hours worked per day for a given employee.

A day is considered to be a tiring day if and only if the number of hours worked is (strictly) greater than 8.

A well-performing interval is an interval of days for which the number of tiring days is strictly larger than the number of non-tiring days.

Return the length of the longest well-performing interval.

This basically translates to finding the longest subarray whose sum is greater than or equal to 0.

Example 1:

Input: hours = [9,9,6,0,6,6,9]

Output: 3

Explanation: The longest well-performing interval is [9,9,6].

Answer 3

Approach:

Standard subarray problem.

Use prefix cumulative sum along with hashmap to track its first occurrence and the index at which it occurred.

public int longestWPI(int[] hours) {
HashMap< Integer,Integer> prefixIdMap = new HashMap< Integer, Integer>();
int res=0;
int prefix=0;

for(int i=0;i< hours.length;i++){
if(hours[i]> 8)prefix++;
else prefix–;

//If we find an i whose prefix is greater than 0, then subArray 0 to i is well performing and we can simply update the result to i+1;
if(prefix> 0)
res=i+1;
//search in the map if (prefix-1) key exists. If such key exists and has some idx as value. Then the subarray [idx+1,i] will be a well performing array.
else{
if(prefixIdMap.get(prefix-1)!=null)
res=Math.max(res,i-prefixIdMap.get(prefix-1));
}
//Don’t put in the map if key already exists, so we always have the leftmost occurances stored in the map of any prefix value.
if(!prefixIdMap.containsKey(prefix))
prefixIdMap.put(prefix,i);
}
return res;
}

Question 4

(Medium) Find Two Non-overlapping Sub-arrays Each With Target Sum

Given an array of integers arr and an integer target.

You have to find two non-overlapping sub-arrays of arr each with sum equal target. There can be multiple answers so you have to find an answer where the sum of the lengths of the two sub-arrays is minimum.

Example 1:

Input: arr = [3,2,2,4,3], target = 3
Output: 2

Explanation: Only two sub-arrays have sum = 3 ([3] and [3]). The sum of their lengths is 2.

Example 2:

Input: arr = [7,3,4,7], target = 7

Output: 2

Answer 4

Approach:

1. Form the Prefix sum in hashmap
2. Iterate over the array & for every index, i check for sum-k in hashmap which signifies subarray ending at i and maintain the minLength.
3. Check for sum+k in hashmap which signifies subarray starting at i+1.

these will be disjoint and if both left & right min are present update & maintain the least res found.

lmin = Math.min(lmin, i-map.get(sum-target));
res = Math.min(res, lmin + map.get(sum+target)-i);

public int minSumOfLengths(int[] arr, int target) { 
 HashMap\< Integer,Integer\> map = new HashMap(); 
 map.put(0,-1);
 int sum=0;
 for(int i=0;i\< arr.length;i++){
 sum+=arr[i]; 
 map.put(sum,i);
 }
 sum=0;
 int lmin=Integer.MAX\_VALUE;
 int res=Integer.MAX\_VALUE;
 for(int i=0;i\< arr.length;i++){
 sum+=arr[i];
 if(map.containsKey(sum-target)){
 lmin = Math.min(lmin, i-map.get(sum-target));
 }
 if(map.containsKey(sum+target) && lmin<integer.max_value></integer.max_value> res = Math.min(res, lmin + map.get(sum+target)-i);
 }
 }
 return res!=Integer.MAX\_VALUE ? res:-1;
 }

Question 5

(Hard) Shortest Subarray with Sum at Least K.

Return the length of the shortest, non-empty, contiguous subarray of A with the sum at least K.

If there is no non-empty subarray with the sum at least K, return -1.

Example 1:

Input: A = [2,-1,2], K = 3

Output: 3

Answer 5

Approach: prefix cumulative sum with Deque.

1. build the prefix sum array.
2. Iterate over the prefix sum array, for every new element
3. pop all the prefix elements which are less than current element, cause now you got a better short answer since we want shortest length.
4. Check for answer with this new element and deque’s last element if the P[j] - P[i] >=K, updated the minRes and pop the deque’s last element, since we only need shortest, even if its a valid element to consider for some idx>j, we don’t need it since we need the shortest.

public int shortestSubarray(int[] A, int K) {
int N = A.length;
long[] P = new long[N+1];
for (int i = 0; i < N; ++i) P[i+1] = P[i] + (long) A[i];

 int ans = Integer.MAX\_VALUE; 
 Deque\< Integer\> monoq = new LinkedList();

for (int y = 0; y < P.length; ++y) {
// If you find a cummulative sum which is less than queue top, keep popping beacuse we want the smallest answer, a smaller cummulative sum is definetly always better than anthing greater than it.
while (!monoq.isEmpty() && P[y] < = P[monoq.getLast()])
monoq.removeLast();
while (!monoq.isEmpty() && P[y] > = P[monoq.getFirst()] + K)
ans = Math.min(ans, y - monoq.removeFirst());
monoq.addLast(y);
System.out.println(Arrays.toString(monoq.toArray()));
}
return ans < N+1 ? ans : -1;
}