LeetCode 1708 - Largest Subarray Length K

LeetCode Problem 1708

Difficulty: 🟢 Easy
Topics: Array, Greedy

Solution

Problem Understanding

The problem asks us to find the lexicographically largest contiguous subarray of length k from a given array of distinct integers.

Two arrays are compared lexicographically. This means we compare elements from left to right until we find the first position where the arrays differ. The array with the larger value at that position is considered larger.

For example:

• [5,2,3] is larger than [4,9,9] because the first differing element is at index 0, and 5 > 4.
• [1,4,7] is larger than [1,3,100] because the first differing element is at index 1, and 4 > 3.

The input consists of:

• nums, an array of distinct integers
• k, the required subarray length

We must return the contiguous subarray of size k that is lexicographically largest among all possible subarrays of that length.

Since all integers are distinct, the comparison between two subarrays becomes simpler. The first element immediately determines which subarray is larger unless the first elements are equal, which cannot happen because all numbers are unique.

The constraints are important:

• nums.length can be as large as 10^5
• A quadratic solution would be too slow
• The integers are distinct, which creates a very useful property for optimization

Important edge cases include:

• k = 1, where we simply return the maximum element
• k = nums.length, where the entire array is the only possible answer
• Arrays where the maximum value appears near the end
• Very large arrays where inefficient comparisons would timeout

The problem guarantees that all values are unique, which is the key observation enabling a very efficient greedy solution.

Approaches

Brute Force Approach

The brute force solution generates every possible subarray of length k and compares them lexicographically to determine the largest one.

There are n - k + 1 possible subarrays. For each candidate subarray, we may need up to k comparisons to determine whether it is larger than the current best.

The algorithm works as follows:

1. Start with the first subarray as the current best.
2. Generate every other subarray of length k.
3. Compare the current candidate with the best subarray element by element.
4. Replace the best subarray if the candidate is lexicographically larger.

This approach is correct because it explicitly checks every valid possibility. However, it is inefficient because repeated lexicographical comparisons can cost up to O(k) each.

In the worst case:

• Number of subarrays: O(n)
• Cost per comparison: O(k)

Overall complexity becomes O(n * k).

With n up to 10^5, this can become too slow.

Optimal Greedy Approach

The key insight comes from the fact that all numbers are distinct.

Because every value is unique, two subarrays can never start with the same element. That means the first element alone determines which subarray is lexicographically larger.

For example:

• [5,2,3] is automatically larger than [4,100,200]
• We never need to compare later elements once the first element differs

Therefore, the problem reduces to finding the largest possible starting element among all valid subarray starting positions.

A valid subarray of length k can start at indices:

0 to n - k

So we simply scan this range and choose the index containing the maximum value.

This produces an O(n) solution with constant extra space.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * k)	O(1)	Compares every subarray lexicographically
Optimal	O(n)	O(1)	Uses the distinct-element property to compare only first elements

Algorithm Walkthrough

Optimal Greedy Algorithm

1. Compute the last valid starting index.

A subarray of length k starting at index i ends at index i + k - 1.

Therefore:

i + k - 1 < n

Rearranging:

i <= n - k

So valid starting positions are from 0 through n - k. 2. Initialize the best starting index.

Start by assuming index 0 is the best starting point. 3. Iterate through all valid starting positions.

For each index i from 1 to n - k:

• Compare nums[i] with nums[best_index]
• If nums[i] is larger, update best_index

4. Extract the answer.

Once the scan is complete, return:

nums[best_index : best_index + k]

5. Return the resulting subarray.

Why it works

Because all integers are distinct, two candidate subarrays always differ at their first element. Lexicographical comparison stops at the first differing position, so the subarray with the larger first element is always larger overall.

Therefore, choosing the maximum possible starting element guarantees the lexicographically largest subarray.

Python Solution

from typing import List

class Solution:
    def largestSubarray(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)

        best_index = 0

        for i in range(1, n - k + 1):
            if nums[i] > nums[best_index]:
                best_index = i

        return nums[best_index:best_index + k]

The implementation begins by storing the array length in n.

We then track the best starting position using best_index. Initially, the first valid subarray is assumed to be the best.

The loop iterates through every valid starting position from 1 to n - k.

At each step, we compare the current starting value with the best starting value seen so far. Since all numbers are distinct, the larger starting value immediately determines the larger subarray.

Finally, we return the slice of length k beginning at best_index.

The Python slicing operation automatically creates the required subarray.

Go Solution

func largestSubarray(nums []int, k int) []int {
	n := len(nums)

	bestIndex := 0

	for i := 1; i <= n-k; i++ {
		if nums[i] > nums[bestIndex] {
			bestIndex = i
		}
	}

	return nums[bestIndex : bestIndex+k]
}

The Go implementation closely mirrors the Python solution.

Instead of Python slicing syntax, Go uses slice ranges:

nums[bestIndex : bestIndex+k]

Go slices reference the original underlying array rather than copying elements immediately. This is efficient and perfectly acceptable for LeetCode submissions.

No special handling for integer overflow is necessary because comparisons are simple and the constraints fit comfortably within Go's integer range.

Worked Examples

Example 1

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

Valid starting indices:

0 to 2

Possible subarrays:

Start Index	Subarray
0	[1,4,5]
1	[4,5,2]
2	[5,2,3]

Algorithm trace:

i	nums[i]	Current Best	Action
0	1	1	Initialize
1	4	1	Update best_index to 1
2	5	4	Update best_index to 2

Final answer:

[5,2,3]

Example 2

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

Valid starting indices:

0 to 1

Possible subarrays:

Start Index	Subarray
0	[1,4,5,2]
1	[4,5,2,3]

Algorithm trace:

i	nums[i]	Current Best	Action
0	1	1	Initialize
1	4	1	Update best_index to 1

Final answer:

[4,5,2,3]

Example 3

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

Valid starting indices:

0 to 4

Each subarray contains one element:

[1], [4], [5], [2], [3]

Algorithm trace:

i	nums[i]	Current Best	Action
0	1	1	Initialize
1	4	1	Update
2	5	4	Update
3	2	5	No change
4	3	5	No change

Final answer:

[5]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single scan through all valid starting positions
Space	O(1)	Only a few variables are used

The algorithm performs exactly one pass through the valid starting indices. Each iteration performs a constant-time comparison.

No auxiliary data structures are needed, so the extra space usage remains constant.

The returned subarray itself is not counted as extra space.

Test Cases

from typing import List

class Solution:
    def largestSubarray(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)

        best_index = 0

        for i in range(1, n - k + 1):
            if nums[i] > nums[best_index]:
                best_index = i

        return nums[best_index:best_index + k]

sol = Solution()

# Provided examples
assert sol.largestSubarray([1,4,5,2,3], 3) == [5,2,3]  # standard example
assert sol.largestSubarray([1,4,5,2,3], 4) == [4,5,2,3]  # only two candidates
assert sol.largestSubarray([1,4,5,2,3], 1) == [5]  # single element subarray

# Entire array
assert sol.largestSubarray([7,8,9], 3) == [7,8,9]  # only one possible subarray

# Maximum at beginning
assert sol.largestSubarray([9,1,2,3,4], 2) == [9,1]  # best starts at index 0

# Maximum at end valid position
assert sol.largestSubarray([1,2,3,9,5], 2) == [9,5]  # best starts at last valid index

# Smallest valid input
assert sol.largestSubarray([42], 1) == [42]  # single element array

# Descending array
assert sol.largestSubarray([9,8,7,6,5], 3) == [9,8,7]  # first subarray largest

# Ascending array
assert sol.largestSubarray([1,2,3,4,5], 2) == [5] if False else [4,5]  # last valid start

# Mixed ordering
assert sol.largestSubarray([3,1,5,2,4], 2) == [5,2]  # internal maximum

Test Case Summary

Test	Why
[1,4,5,2,3], k=3	Standard example from prompt
[1,4,5,2,3], k=4	Only two candidate subarrays
[1,4,5,2,3], k=1	Single-element subarrays
[7,8,9], k=3	Entire array returned
[9,1,2,3,4], k=2	Best subarray starts at index 0
[1,2,3,9,5], k=2	Best subarray starts at last valid index
[42], k=1	Smallest possible input
[9,8,7,6,5], k=3	Descending order
[1,2,3,4,5], k=2	Ascending order
[3,1,5,2,4], k=2	Maximum element in middle

Edge Cases

Case 1: k = 1

When k equals 1, every subarray contains only a single element. The problem becomes equivalent to finding the maximum value in the array.

This can expose bugs if the implementation incorrectly assumes multi-element comparisons are necessary.

The current solution handles this naturally because it simply selects the largest valid starting element.

Case 2: k = nums.length

When the subarray length equals the entire array length, there is only one possible subarray.

A buggy implementation might incorrectly iterate beyond valid boundaries or assume multiple candidates exist.

The algorithm correctly computes:

n - k = 0

So only index 0 is considered, and the entire array is returned.

Case 3: Largest Element Near the End

Consider:

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

The best subarray begins at the final valid starting index.

This case is important because off-by-one errors commonly occur when computing:

n - k

The loop condition:

range(1, n - k + 1)

ensures the final valid starting position is included.

Case 4: Strictly Descending Array

Consider:

nums = [9,8,7,6,5]

A naive intuition might incorrectly assume later positions could still produce larger subarrays due to later elements.

However, lexicographical comparison depends entirely on the earliest differing position. Since the first element of the first subarray is already the maximum possible, the first subarray remains optimal.

The implementation correctly preserves the earliest maximum starting value.