Leetcode 1708. Largest Subarray Length K

Problem Description

In this problem, you are given an integer array nums of distinct integers. You are asked to return the largest subarray of nums of length k. The first step is to comprehend how an array is considered to be larger than another. An array A is larger than some array B if, for the first index i where A[i] != B[i], A[i] > B[i].

Example

Let's walk through an example to better understand the problem:

1nums = [1,4,5,2,3]
2k = 3

The subarrays of size 3 are: [1,4,5], [4,5,2], and [5,2,3]. We will compare these subarrays to find the largest one.

Comparing [1,4,5] and [4,5,2]:

At index 0, 1 < 4, thus [1,4,5] < [4,5,2].

Comparing [4,5,2] and [5,2,3]:

At index 0, 4 < 5, thus [4,5,2] < [5,2,3].

So, the largest subarray of nums of length 3 is: [5,2,3]

Approach

We will use a sliding window approach for this problem. We will start initializing a window of size k, and iterate through the array comparing the subarrays within the window. During each iteration, we'll move the window to the right and compare the new subarray against the previous largest subarray.

Python Solution

1class Solution:
2    def largest_subarray(self, nums, k):
3        n = len(nums)
4        max_subarray = nums[:k]
5        
6        for i in range(1, n - k + 1):
7            current_subarray = nums[i:i + k]
8            if current_subarray > max_subarray:
9                max_subarray = current_subarray
10                
11        return max_subarray

Java Solution

1import java.util.Arrays;
2
3class Solution {
4    public int[] largestSubarray(int[] nums, int k) {
5        int n = nums.length;
6        int[] maxSubarray = Arrays.copyOfRange(nums, 0, k);
7        
8        for (int i = 1; i <= n - k; i++) {
9            int[] currentSubarray = Arrays.copyOfRange(nums, i, i + k);
10            if (greater(currentSubarray, maxSubarray)) {
11                maxSubarray = currentSubarray;
12            }
13        }
14        
15        return maxSubarray;
16    }
17    
18    public boolean greater(int[] current, int[] max) {
19        for (int i = 0; i < current.length; i++) {
20            if (current[i] != max[i]) {
21                return current[i] > max[i];
22            }
23        }
24        return false;
25    }
26}

JavaScript Solution

1class Solution {
2    largestSubarray(nums, k) {
3        const n = nums.length;
4        let maxSubarray = nums.slice(0, k);
5        
6        for (let i = 1; i <= n - k; i++) {
7            const currentSubarray = nums.slice(i, i + k);
8            if (currentSubarray > maxSubarray) {
9                maxSubarray = currentSubarray;
10            }
11        }
12        
13        return maxSubarray;
14    }
15}

C++ Solution

1#include <vector>
2
3class Solution {
4public:
5    std::vector<int> largestSubarray(std::vector<int>& nums, int k) {
6        int n = nums.size();
7        std::vector<int> maxSubarray(nums.begin(), nums.begin() + k);
8        
9        for (int i = 1; i <= n - k; i++) {
10            std::vector<int> currentSubarray(nums.begin() + i, nums.begin() + i + k);
11            if (currentSubarray > maxSubarray) {
12                maxSubarray = currentSubarray;
13            }
14        }
15        
16        return maxSubarray;
17    }
18};

C# Solution

1using System;
2
3public class Solution {
4    public int[] LargestSubarray(int[] nums, int k) {
5        int n = nums.Length;
6        int[] maxSubarray = new int[k];
7        Array.Copy(nums, maxSubarray, k);
8        
9        for (int i = 1; i <= n - k; i++) {
10            int[] currentSubarray = new int[k];
11            Array.Copy(nums, i, currentSubarray, 0, k);
12            
13            if(Greater(currentSubarray, maxSubarray)) {
14                maxSubarray = currentSubarray;
15            }
16        }
17        
18        return maxSubarray;
19    }
20
21    public bool Greater(int[] current, int[] max) {
22        for (int i = 0; i < current.Length; i++) {
23            if (current[i] != max[i]) {
24                return current[i] > max[i];
25            }
26        }
27        return false;
28    }
29}

Conclusion

In this article, we discussed the problem of finding the largest subarray of size k in a given integer array. We presented the sliding window approach and then provided solutions in 5 different programming languages: Python, Java, JavaScript, C++, and C#. These solutions should provide a good understanding of the problem and a basis to implement your own solution if needed.