1708. Largest Subarray Length K

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

 

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

Rust Solution

struct Solution;

impl Solution {
    fn largest_subarray(nums: Vec<i32>, k: i32) -> Vec<i32> {
        let n = nums.len();
        let k = k as usize;
        let mut j = 0;
        for i in 1..=n - k {
            if nums[i] > nums[j] {
                j = i;
            }
        }
        nums[j..j + k].to_vec()
    }
}

#[test]
fn test() {
    let nums = vec![1, 4, 5, 2, 3];
    let k = 3;
    let res = vec![5, 2, 3];
    assert_eq!(Solution::largest_subarray(nums, k), res);
    let nums = vec![1, 4, 5, 2, 3];
    let k = 4;
    let res = vec![4, 5, 2, 3];
    assert_eq!(Solution::largest_subarray(nums, k), res);
    let nums = vec![1, 4, 5, 2, 3];
    let k = 1;
    let res = vec![5];
    assert_eq!(Solution::largest_subarray(nums, k), res);
}

Having problems with this solution? Click here to submit an issue on github.