Grokking Data Structures & Algorithms for Coding Interviews

0% completed

​

Solution: Max of All Subarrays of Size 'k'

Problem Statement

Given an integer array arr and an integer k, return the result list containing the maximum for each and every contiguous subarray of size k.

In other words, result[i] = max(arr[0],..., arr[k]), result[1] = max(arr[1],...arr[k+1]), etc.

Examples

Example 1

  • Input: arr = [1, 2, 3, 1, 4, 5, 2, 3, 6], k = 3
  • Output: [3, 3, 4, 5, 5, 5, 6]
  • Description: Here, subarray [1,2,3] has maximum 3, [2,3,1] has maximum 3, [3,1,4] has maximum 4, [1,4,5] has maximum 5, [4,5,2] has maximum 5, [5,2,3] has maximum 5, and

.....

.....

.....

Like the course? Get enrolled and start learning!
K

Kartheek Penagamuri

· 3 years ago

The following solution also passed all the test cases. When compared to the solution provided by the author, the only difference is that I used if block to remove out of range elements from the dequeue instead of a while loop. I am having hard time to come up with a test case where my code fails but the solution that has while loop to remove out of range elements from the dequeue succeeds.

public class Solution {

public List<int> printMax(int[] arr, int k) {

    List<int> result = new List<int>();

    // ToDo: Write Your Code Here.

    LinkedList<int> dequeue = new LinkedList<int>();



    for (int i = 0; i < arr.Length; i++) 

    {

        if (dequeue.Count > 0 && dequeue.First.Value < i - k + 1)

            dequeue.RemoveFirst();
K

kurtbell87

· 2 years ago

I understand the purpose of this module is using queues. What I don't understand is if this smaller more compact method is less efficient somehow

Show 1 reply
L

lestatcheb

· 2 years ago

The space complexity of this algorithm is O(k), where k is the size of the window.

Since we need to return a result of basically size n, I think space complexity is O(n) here, no?

T

Tony Pham

· 2 years ago

Here's my solution to this.

def max_subarray(arr, k):
	dq = deque()
	result = []

	for end in range(len(arr)):
	    if dq and dq[0] == end - k:
	        dq.popleft()

	    while dq and arr[dq[-1]] <= arr[end]:
	        dq.pop()

	    dq.append(end)

	    if end >= k - 1:
	        result.append(arr[dq[0]])

	return result
Sourav Singh

Sourav Singh

· 2 years ago

func (s *Solution) printMax(arr []int, k int) []int {
    result := []int{}
    queue := []int{}

    for i := 0; i < len(arr); i++ {
        if len(queue) > 0 && queue[0] < i-k+1 {
            queue = queue[1:]
        }

        for len(queue) > 0 && arr[queue[len(queue)-1]] < arr[i] {
            queue = queue[:len(queue)-1]
        }

        queue = append(queue, i)

        if i >= k-1 {
            result = append(result, arr[queue[0]])
        }
    }
    return result
}
Show 1 reply
N

n.place

· 10 months ago

This approach always guarantees that the front of the queue for a given window is the greatest in a given window, but by removing smaller elements from the front rather than the rear


class Solution {
    printMax(arr, k) {
        let result = [];
        let deque = new Deque()
        let left = 0
        let right = k - 1

        // setup
        for (let i = 0; i < right; i++) {
            while (!deque.isEmpty() && arr[deque.getFront()] < arr[i]) {
                deque.removeFront()
            }
            deque.addRear(i)
        }

        // main loop
        while (right < arr.length) {
            while (!deque.isEmpty() && (arr[deque.getFront()] < arr[right] || deque.getFront() < left)) {
                deque.removeFront()
            }
            deque.addRear(ri