Problem

An array A is larger than some array B if for the first index i where A[i] != B[i], A[i] > B[i].

For example, consider 0-indexing:

  • [1,3,2,4] > [1,2,2,4], since at index 1, 3 > 2.
  • [1,4,4,4] < [2,1,1,1], since at index 0, 1 < 2.

A subarray is a contiguous subsequence of the array.

Given an integer array nums of distinct integers, return the largest subarray of nums of length k.

Examples

Example 1:

1
2
3
4

Input: nums = [1,4,5,2,3], k = 3
Output: [5,2,3]
Explanation: The subarrays of size 3 are: [1,4,5], [4,5,2], and [5,2,3].
Of these, [5,2,3] is the largest.

Example 2:

1
2
3
4

Input: nums = [1,4,5,2,3], k = 4
Output: [4,5,2,3]
Explanation: The subarrays of size 4 are: [1,4,5,2], and [4,5,2,3].
Of these, [4,5,2,3] is the largest.

Example 3:

1
2

Input: nums = [1,4,5,2,3], k = 1
Output: [5]

Constraints:

  • 1 <= k <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • All the integers of nums are unique.

Follow up: What if the integers in nums are not distinct?

Solution

Method 1 – Sliding Window Maximum

Intuition

To find the lexicographically largest subarray of length k, we need the subarray that starts at the position of the largest element among all possible starting positions. Since all elements are distinct, the largest subarray will start at the largest element in the first n-k+1 positions.

Approach

  1. Iterate through all possible starting indices from 0 to n-k.
  2. Track the subarray of length k with the largest first element (and compare lexicographically if needed).
  3. Return the subarray found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
public:
    vector<int> largestSubarray(vector<int>& nums, int k) {
        int n = nums.size(), idx = 0;
        for (int i = 1; i <= n - k; ++i) {
            if (nums[i] > nums[idx]) idx = i;
        }
        return vector<int>(nums.begin() + idx, nums.begin() + idx + k);
    }
};
1
2
3
4
5
6
7

func largestSubarray(nums []int, k int) []int {
    idx := 0
    for i := 1; i <= len(nums)-k; i++ {
        if nums[i] > nums[idx] { idx = i }
    }
    return nums[idx:idx+k]
}
1
2
3
4
5
6
7
8
9

class Solution {
    public int[] largestSubarray(int[] nums, int k) {
        int idx = 0, n = nums.length;
        for (int i = 1; i <= n - k; ++i) {
            if (nums[i] > nums[idx]) idx = i;
        }
        return Arrays.copyOfRange(nums, idx, idx + k);
    }
}
1
2
3
4
5
6
7
8
9

class Solution {
    fun largestSubarray(nums: IntArray, k: Int): IntArray {
        var idx = 0
        for (i in 1..nums.size-k) {
            if (nums[i] > nums[idx]) idx = i
        }
        return nums.sliceArray(idx until idx+k)
    }
}
1
2
3
4
5
6
7

class Solution:
    def largestSubarray(self, nums: list[int], k: int) -> list[int]:
        idx = 0
        for i in range(1, len(nums)-k+1):
            if nums[i] > nums[idx]:
                idx = i
        return nums[idx:idx+k]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

impl Solution {
    pub fn largest_subarray(nums: Vec<i32>, k: i32) -> Vec<i32> {
        let n = nums.len();
        let mut idx = 0;
        for i in 1..=n-k as usize {
            if nums[i] > nums[idx] { idx = i; }
        }
        nums[idx..idx+k as usize].to_vec()
    }
}
1
2
3
4
5
6
7
8
9

class Solution {
    largestSubarray(nums: number[], k: number): number[] {
        let idx = 0
        for (let i = 1; i <= nums.length - k; ++i) {
            if (nums[i] > nums[idx]) idx = i
        }
        return nums.slice(idx, idx + k)
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of nums. Each element is checked once.
  • 🧺 Space complexity: O(k), for the result subarray.