Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1708.html

1708. Largest Subarray Length K

Level

Easy

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 <= 10^5
  • 1 <= nums[i] <= 10^9
  • All the integers of nums are unique.

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

Solution

Since all the integers in the array are unique, the largest subarray is the subarray that has the largest starting value. Loop over the elements from index 0 to index nums.length - k and find the largest element and the corresponding index. Return the subarray starting from the index.

  • class Solution {
    public int[] largestSubarray(int[] nums, int k) {
        int maxStart = nums.length - k;
        int maxNum = nums[0], maxIndex = 0;
        for (int i = 1; i <= maxStart; i++) {
            int num = nums[i];
            if (num > maxNum) {
                maxNum = num;
                maxIndex = i;
            }
        }
        int[] subarray = new int[k];
        System.arraycopy(nums, maxIndex, subarray, 0, k);
        return subarray;
    }
}

############

class Solution {
    public int[] largestSubarray(int[] nums, int k) {
        int i = 0, mx = 0;
        for (int j = 0; j < nums.length - k + 1; ++j) {
            if (mx < nums[j]) {
                mx = nums[j];
                i = j;
            }
        }
        int[] ans = new int[k];
        for (int j = 0; j < k; ++j) {
            ans[j] = nums[i + j];
        }
        return ans;
    }
}

  • // OJ: https://leetcode.com/problems/largest-subarray-length-k/
// Time: O(N)
// Space: O(1) extra space
class Solution {
public:
    vector<int> largestSubarray(vector<int>& A, int k) {
        auto it = max_element(begin(A), end(A) - k + 1);
        return vector<int>(it, it + k);
    }
};

  • class Solution:
    def largestSubarray(self, nums: List[int], k: int) -> List[int]:
        mx = max(nums[: len(nums) - k + 1])
        i = nums.index(mx)
        return nums[i : i + k]



  • func largestSubarray(nums []int, k int) []int {
	i, mx := 0, 0
	for j := 0; j < len(nums)-k+1; j++ {
		if mx < nums[j] {
			mx = nums[j]
			i = j
		}
	}
	return nums[i : i+k]
}

  • impl Solution {
    #[allow(dead_code)]
    pub fn largest_subarray(nums: Vec<i32>, k: i32) -> Vec<i32> {
        let mut ret_vec = vec![i32::MIN];
        let n = nums.len();

        if n == k as usize {
            return nums;
        }

        for i in 0..=n - k as usize {
            if nums[i] > ret_vec[0] {
                ret_vec = nums[i..i + k as usize].to_vec();
            }
        }

        ret_vec
    }
}

  • 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);
}

All Problems

All Solutions