We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Largest Subarray Length K

Number: 1847

Difficulty: Easy

Paid? Yes

Companies: Google

Problem Description

Given an array of distinct integers and an integer k, find the largest contiguous subarray of length k. An array A is considered larger than an array B if at the first index where they differ, the element in A is greater than the corresponding element in B.

For example: • For nums = [1,4,5,2,3] and k = 3, the available subarrays are [1,4,5], [4,5,2], and [5,2,3]. The subarray [5,2,3] is the largest since 5 > 1 and 5 > 4. • For nums = [1,4,5,2,3] with k = 4, the subarrays [1,4,5,2] and [4,5,2,3] yield [4,5,2,3] as the largest because 4 > 1. • For k = 1, it is simply the maximum element in the array as a single element subarray.

Key Insights

  • Only contiguous subarrays of length k are allowed.
  • Since the integers in nums are distinct, comparing two subarrays lexicographically primarily comes down to comparing their first elements.
  • The largest subarray of length k is determined by the maximum element among the valid starting positions (from index 0 to n-k).
  • After finding the optimal starting index, the answer is the subarray of length k starting at that index.

Space and Time Complexity

Time Complexity: O(n) – We scan from index 0 to (n - k) once to find the maximum starting element. Space Complexity: O(1) – Only a few extra variables are used.

Solution

The approach involves determining the valid range of starting indices. Only indices from 0 to (n - k) can be the start of a contiguous subarray of length k. Since the numbers are distinct, the lexicographical order between any two subarrays is decided at the first element. Therefore, simply traverse the indices 0 to (n - k) to identify the index with the maximum value. Once found, return the contiguous subarray starting at that index of length k.

Code Solutions

# Python solution
def largestSubarray(nums, k):
    # Calculate the maximum starting index for a valid subarray of length k
    max_start = 0
    # Iterate over valid starting indices (0 to len(nums) - k)
    for i in range(1, len(nums) - k + 1):
        # Update max_start if a larger starting element is found
        if nums[i] > nums[max_start]:
            max_start = i
    # Return the subarray of length k starting at max_start
    return nums[max_start:max_start + k]

# Example usage:
print(largestSubarray([1,4,5,2,3], 3))  # Output: [5,2,3]
← Back to All Questions