Tag Archives: Sliding Window

Subarray with Given Sum

By | | , , ,
Leave a comment

Find subarray with given sum.

Given an array of unsorted integers (Positive integers), We have to write a code to find a subarray whose sum is equal to a given sum.

We have to return subarray indexes (start and end index).

For Example –

  Example 1 :

Input : arr = {10, 2, 4, 7, 5}, sum = 13

Output: {1, 3}

The numbers present from the 1st to 3rd indexes are 2, 4, 7. When we add (2 + 4 + 7) it is 13.

Example 2 :

Input : arr = {1, 4, 20, 3, 10, 5}, sum = 33

  Output: {2, 4}

Example 3 :

  Input : arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, sum = 15

   Output: {0, 4}

→

Count Distinct Elements in Every Window of Size K

By | | , ,
Leave a comment

Count Distinct Elements in Every Window of Size K.

Given an array of n integers and an integer k (k is always smaller or equal to n).  Return the count of distinct elements in all windows (or in all sub-arrays) of size k.

For example –

   Example 1:

  Input: {1, 5, 9, 3, 3, 7, 3},   k = 3

  Output: {3, 3, 2, 2, 2}

1st window {1, 5, 9}, Distinct elements are 3.

2nd window {5, 9, 3}, Distinct elements are 3.

3rd window {9, 3, 3}, Distinct elements are 2.

4th window {3, 3, 7}, Distinct elements are 2.

5th window {3, 7, 3}, Distinct elements are 2.

   Example 2:

  Input: {1, 4, 7, 7},   k = 2

  Output: {2, 2, 1}

1st window {1, 4}, Distinct elements are 2.

2nd window {4, 7}, Distinct elements are 2.

3rd window {7, 7}, Distinct elements are 1.

→

Maximum Consecutive Ones III

By | | , ,
Leave a comment

Maximum consecutive ones III. Find maximum consecutive ones in an array of 0s and 1s, If k flip is allowed.

Given an array which only consists of 0s and 1s. Write a code to find the maximum number of consecutive 1s in an array, if we can flip k zeros.

For example:

Input – {1, 1, 0, 0, 0, 1, 1, 1, 1, 1}, k = 2 (We can flip two zeros)

Output: 7

Explanation:

In this example, If we can flip at most k (which is 2) zero. By flipping the zeros, here we can form following subarrays.

{1, 1, 1, 1} -> From index 0 to 3 (zero is present at index 2 and 3)

One subarray is from index 1 to 3 -> {1, 1, 1}

Another subarray is from index 2 to 3 (As both the element at this index is zero) -> {1, 1}

From index 3 to 9 -> {1, 1, 1, 1, 1, 1, 1}

Out of these, the maximum number of consecutive 1s in an array is 7 {1, 1, 1, 1, 1, 1, 1}.

→