Skip to content

1708. Largest Subarray Length K πŸ”’

DifficultyEasy

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 \(\textit{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)\), and the space complexity is \(O(1)\), where \(n\) is the length of the array.

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