Skip to content

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 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 <= 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

Thinking

Among subarrays of length \(k\), the lexicographically largest is decided by its first element, since all values are distinct.

Valid starts lie in \([0,n-k]\). Take the index \(i\) of the maximum in that range; the answer is \(nums[i..i+k)\). One scan suffices.

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
class Solution:
    def largestSubarray(self, nums: List[int], k: int) -> List[int]:
        i = nums.index(max(nums[: len(nums) - k + 1]))
        return nums[i : i + k]

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

1
2
3
4
5
6
7
class Solution {
public:
    vector<int> largestSubarray(vector<int>& nums, int k) {
        auto i = max_element(nums.begin(), nums.end() - k + 1);
        return {i, i + k};
    }
};

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

1
2
3
4
5
6
7
8
9
function largestSubarray(nums: number[], k: number): number[] {
    let j = 0;
    for (let i = 1; i < nums.length - k + 1; ++i) {
        if (nums[j] < nums[i]) {
            j = i;
        }
    }
    return nums.slice(j, j + k);
}

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

Comments