Grokking Data Structures & Algorithms for Coding Interviews
Vote

0% completed

​

Max of All Subarrays of Size 'k' (medium)

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 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
A

Anonymous

· 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
A

Anonymous

· 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?

A

Anonymous

· 3 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
A

Anonymous

· 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();

Reading Progress

0%

Vote for new content