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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.