Problem statement

https://leetcode.com/problems/largest-subarray-length-k/

Solution

It is given that all numbers are distinct, so we need to start from the biggest one: we need to make sure that we have enough space, so we can start with 0, ..., n-k places.

Complexity

Time complexity is O(n), space is O(k) to return answer.

Code

class Solution:
    def largestSubarray(self, nums, k):
        n = len(nums)
        idx = max((nums[i], i) for i in range(n-k+1))
        return nums[idx[1]:idx[1] + k]

Solution for follow-up

Follow up question asks what to do if we have duplicates. It is similar to problem 1163 Last Substring in Lexicographical Order: there is O(n) solution with two pointers.

Complexity

It is O(n) for time and O(k) for space

Code

class Solution:
    def largestSubarray(self, s, k):
        i, j, l = 0, 1, 0
        n = len(s) - k + 1
        while j + l < n:
            if s[i+l] == s[j+l]:
                l += 1
                continue
            elif s[i+l] > s[j+l]:
                j = j + l + 1
            else:
                i = max(i + l + 1, j)
                j = i + 1
            l = 0
        return s[i:i+k]

Remark

It also can be solved with suffix arrays.