1708. Largest Subarray Length K π
Description
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 index1
,3 > 2
.[1,4,4,4] < [2,1,1,1]
, since at index0
,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 <= 105
1 <= nums[i] <= 109
- All the integers of
nums
are unique.
Follow up: What if the integers in nums
are not distinct?
Solutions
Solution 1: Simulation
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)$.
1 2 3 4 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 |
|
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|