Amazon OA | Hard problem
Anonymous User
772
AmazonArrayInterview

Can anyone provide efficient solution to this problem?
I was able to brute force but unable to optimise as the array can be as long as 3 * 10^5

image

image

EDIT:

Here is the brute force as requested by someone in comments

def findKthMinimumVulnerability(vulnerability, k, m):
    n = len(vulnerability)
    ans = []
    
    window = []
    for i in range(m-1):
        window.append(vulnerability[i])
    
    left = 0
    for i in range(m-1, n):
        window.append(vulnerability[i])
        ans.append(sorted(window)[k-1])
        window.remove(vulnerability[left])
        left += 1
    
    return ans

print(findKthMinimumVulnerability([1,3,2,1], 2, 3))
print(findKthMinimumVulnerability([4,2,3,1,1], 3, 4))

TC: O(nmlogm)

If anyone can post optimised version of this, it will be very helpful.

Comments (10)