Skip to main content
Talentd

Largest Subarray Length K - Solution & Explanation

EasyPremiumFree on FleetCodeArrayGreedy6 min readAsked at: Google
Practice this problem

Problem Statement

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 <= 105
  • 1 <= nums[i] <= 109
  • All the integers of nums are unique.

 

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

Approach Overview

Problem Overview: Given an integer array nums with distinct values and an integer k, return the subarray of length k that is lexicographically largest. Among all contiguous subarrays of size k, choose the one whose sequence would appear last in dictionary order.

Approach 1: Simulation / Compare All Subarrays (O(n * k) time, O(1) extra space)

The direct approach checks every possible starting position from index 0 to n - k. For each start index, compare the current length‑k window with the best subarray found so far using lexicographical comparison. This means iterating element‑by‑element until a difference is found. The approach is simple and mirrors how dictionary ordering works, but the comparison step costs up to k operations for each of the n - k + 1 windows. This leads to O(n * k) time complexity with constant extra space. Use this when constraints are small or when implementing a quick correctness-first solution.

Approach 2: Greedy - Max First Element (O(n) time, O(1) extra space)

A key observation simplifies the problem: the array contains distinct integers. In lexicographical comparison, the first element decides the ordering unless two prefixes are identical. Because all values are distinct, the subarray whose first element is largest must produce the lexicographically largest sequence. You only need to find the maximum value among indices 0 through n - k, since any valid subarray of length k must start within this range. Scan this region once, track the index of the largest element, then return the slice nums[maxIndex : maxIndex + k]. The scan takes O(n) time and uses O(1) extra space besides the output.

This greedy observation removes the need to compare full subarrays and turns the problem into a single pass over the valid start positions. It relies only on simple array traversal and integer comparisons, making it both efficient and easy to implement.

Recommended for interviews: Start by describing the brute force simulation to demonstrate understanding of lexicographic ordering. Then move to the greedy insight: because values are distinct, the largest starting element guarantees the largest subarray. Interviewers typically expect the O(n) greedy scan using basic array traversal and a greedy selection strategy.

Solution

All integers in the array are distinct, so we can first find the index of the maximum element in the range [0,..n-k], and then take k elements starting from this index.

The time complexity is O(n), where n is the length of the array. Ignoring the space consumption of the answer, the space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Simulation / Compare SubarraysO(n * k)O(1)Good for understanding lexicographical comparison or when constraints are small
Greedy Max Start ElementO(n)O(1)Optimal approach when array values are distinct and you need the lexicographically largest window

Video Solution

1708. Largest Subarray Length K (Leetcode Easy) • Programming Live with Larry • 353 views views

Watch 2 more video solutions →

Frequently Asked Questions

Is Largest Subarray Length K easy or hard?
Largest Subarray Length K is classified as Easy. The implementation is short, but the key insight is recognizing that distinct values allow a greedy choice based only on the first element. Once that observation is made, the solution reduces to a single linear scan.
Largest Subarray Length K Python/Java solution
Most implementations follow the same pattern across languages: iterate through indices 0 to n-k, track the index with the largest value, and return nums[start:start+k]. This logic works identically in Python, Java, C++, Go, TypeScript, and Rust with linear O(n) time complexity.
How to solve Largest Subarray Length K in O(n)?
Iterate through the range of valid starting indices from 0 to n-k. Track the index containing the largest element in that range. Once the scan finishes, return the subarray nums[maxIndex : maxIndex + k]. The distinct-value constraint guarantees this start index produces the lexicographically largest sequence.
What is the best approach for Largest Subarray Length K?
The optimal approach is a greedy scan. Because all numbers in the array are distinct, the lexicographically largest subarray must start with the largest possible first element. Scan indices from 0 to n-k, find the maximum value, and return the k-length slice starting there. This runs in O(n) time and O(1) extra space.
Is Largest Subarray Length K asked at Google/Amazon/Meta?
Problems combining array traversal with greedy selection appear frequently in interviews at large tech companies such as Google, Amazon, and Meta. While this exact problem may vary, the core pattern—identifying the best window using a greedy observation—is a common interview theme.
What data structure is used in Largest Subarray Length K?
The problem primarily uses a simple array traversal. No advanced data structures are required for the optimal solution. A few integer variables track the maximum value and its index while scanning the array.
What is the time complexity of Largest Subarray Length K?
The optimal greedy solution runs in O(n) time because it scans the valid starting positions once to find the maximum element. Space complexity is O(1) since only a few variables are used besides the returned subarray. A brute force method that compares every k-length subarray takes O(n * k) time.

Ready to solve this problem?

Practice Largest Subarray Length K with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays