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.
Example 1:
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:
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:
Input: nums = [1,4,5,2,3], k = 1 Output: [5]
Constraints:
1 <= k <= nums.length <= 1051 <= nums[i] <= 109nums are unique.Follow up: What if the integers in
nums are not distinct?Problem Overview: Given an integer array nums with distinct values and an integer k, return the subarray of length k that is lexicographically largest. Among all contiguous subarrays of size k, choose the one whose sequence would appear last in dictionary order.
Approach 1: Simulation / Compare All Subarrays (O(n * k) time, O(1) extra space)
The direct approach checks every possible starting position from index 0 to n - k. For each start index, compare the current length‑k window with the best subarray found so far using lexicographical comparison. This means iterating element‑by‑element until a difference is found. The approach is simple and mirrors how dictionary ordering works, but the comparison step costs up to k operations for each of the n - k + 1 windows. This leads to O(n * k) time complexity with constant extra space. Use this when constraints are small or when implementing a quick correctness-first solution.
Approach 2: Greedy - Max First Element (O(n) time, O(1) extra space)
A key observation simplifies the problem: the array contains distinct integers. In lexicographical comparison, the first element decides the ordering unless two prefixes are identical. Because all values are distinct, the subarray whose first element is largest must produce the lexicographically largest sequence. You only need to find the maximum value among indices 0 through n - k, since any valid subarray of length k must start within this range. Scan this region once, track the index of the largest element, then return the slice nums[maxIndex : maxIndex + k]. The scan takes O(n) time and uses O(1) extra space besides the output.
This greedy observation removes the need to compare full subarrays and turns the problem into a single pass over the valid start positions. It relies only on simple array traversal and integer comparisons, making it both efficient and easy to implement.
Recommended for interviews: Start by describing the brute force simulation to demonstrate understanding of lexicographic ordering. Then move to the greedy insight: because values are distinct, the largest starting element guarantees the largest subarray. Interviewers typically expect the O(n) greedy scan using basic array traversal and a greedy selection strategy.
All integers in the array are distinct, so we can first find the index of the maximum element in the range [0,..n-k], and then take k elements starting from this index.
The time complexity is O(n), where n is the length of the array. Ignoring the space consumption of the answer, the space complexity is O(1).
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulation / Compare Subarrays | O(n * k) | O(1) | Good for understanding lexicographical comparison or when constraints are small |
| Greedy Max Start Element | O(n) | O(1) | Optimal approach when array values are distinct and you need the lexicographically largest window |
1708. Largest Subarray Length K (Leetcode Easy) • Programming Live with Larry • 340 views views
Watch 2 more video solutions →Practice Largest Subarray Length K with our built-in code editor and test cases.
Practice on FleetCode