Maximum Sum of Distinct Subarrays With Length K solution and explanation
IBM
Google
TCS
9 more videos on this problem
Maximum Sum of Distinct Subarrays With Length K - Leetcode 2461 - PythonNeetCodeIO · 16:53 · 19K views
Maximum Sum of Distinct Subarrays With Length K | Classic Sliding Window Template | Leetcode 2461...codestorywithMIK · 19:53 · 15K views
Maximum Sum of Distinct Subarrays With Length K | Leetcode 2461Techdose · 16:08 · 6K views
2461. Maximum Sum of Distinct Subarrays With Length K | Sliding WindowAryan Mittal · 9:34 · 4K views
2461. Maximum Sum of Distinct Subarrays With Length K (Leetcode Medium)Programming Live with Larry · 7:10 · 2K views
LeetCode 2461 Maximum Sum of Distinct Subarrays With Length K | Sliding Window | Amazon | GoogleCode Harmony · 19:07 · 1K views
【每日一题】LeetCode 2461. Maximum Sum of Distinct Subarrays With Length KHuifeng Guan · 8:57 · 385 views
LeetCode 2461 - Maximum Sum of of Distinct Subarrays of Length K - JavaAlpha-Code · 6:19 · 296 views
Daily Leetcode #1694: Nov 19, 2024 - 2461. Maximum Sum of Distinct Subarrays With Length KProgramming Live with Larry · 6:20 · 296 views
subarray with distinct with max.sum easy explanation | leetcode-2461 | in tamilCode Triumph · 14:54 · 278 views
The problem
You are given an integer array nums and an integer k. Find the maximum subarray sum of all the subarrays of nums that meet the following conditions:
- The length of the subarray is
k, and - All the elements of the subarray are distinct.
Return the maximum subarray sum of all the subarrays that meet the conditions. If no subarray meets the conditions, return 0.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [1,5,4,2,9,9,9], k = 3 Output: 15 Explanation: The subarrays of nums with length 3 are: - [1,5,4] which meets the requirements and has a sum of 10. - [5,4,2] which meets the requirements and has a sum of 11. - [4,2,9] which meets the requirements and has a sum of 15. - [2,9,9] which does not meet the requirements because the element 9 is repeated. - [9,9,9] which does not meet the requirements because the element 9 is repeated. We return 15 because it is the maximum subarray sum of all the subarrays that meet the conditions
Example 2:
Input: nums = [4,4,4], k = 3 Output: 0 Explanation: The subarrays of nums with length 3 are: - [4,4,4] which does not meet the requirements because the element 4 is repeated. We return 0 because no subarrays meet the conditions.
Constraints:
1 <= k <= nums.length <= 1051 <= nums[i] <= 105
Approach overview
Problem Overview: Given an integer array and an integer k, find the maximum sum of any subarray of length k where all elements are distinct. If no such subarray exists, return 0. The challenge is enforcing both constraints simultaneously: fixed window size and uniqueness of elements.
Approach 1: Sorting (O(n log n) time, O(n) space)
This approach evaluates every subarray of length k, stores the elements temporarily, and checks if all values are distinct by sorting or using a set. Sorting a window allows you to quickly detect duplicates because equal elements become adjacent. After confirming uniqueness, compute the sum and track the maximum. While straightforward, this method repeatedly sorts windows, making the complexity O(n log k) per window in practice (commonly simplified to O(n log n)). This is mostly useful as a conceptual or brute-force baseline before introducing optimized techniques.
Approach 2: Hash Map for Counting (Sliding Window) (O(n) time, O(k) space)
The optimal solution uses a sliding window combined with a hash table to maintain frequency counts of elements in the current window. Expand the window by moving the right pointer and update the running sum. Each time the window size exceeds k, remove the leftmost element, decrement its count in the hash map, and update the sum. The key condition is checking whether the window contains exactly k distinct elements. When the window length is k and the map size is also k, every element is unique, so the current sum becomes a candidate for the maximum.
This technique avoids recomputing sums or rechecking duplicates from scratch. Every element enters and leaves the window once, giving linear time complexity. The hash map ensures constant-time frequency updates and uniqueness checks. Because the window size never exceeds k, the extra memory stays bounded by O(k). This pattern appears frequently in array problems involving fixed-length windows and uniqueness constraints.
Recommended for interviews: Interviewers expect the sliding window + hash map solution. Starting with the naive window check shows you understand the problem constraints, but optimizing it to a linear-time sliding window demonstrates strong algorithmic thinking and familiarity with common array patterns.
Approach 1: Approach 1: Hash Map for Counting
This approach uses a hash map (or dictionary) to count occurrences of elements in the data. By iterating through the data once to populate the hash map, we can achieve efficient lookups. The main idea is to traverse the input list, counting occurrences of each element, and storing these counts in a hash map for quick access in the future.
def element_count():
count = {}
n = int(input("Enter number of elements: "))
print("Enter the elements:")
for _ in range(n):
x = int(input())
if x in count:
count[x] += 1
else:
count[x] = 1
# Example query
query = int(input("Enter element to query: "))
print(f"Element {query} appears {count.get(query, 0)} times")
# Run the function
element_count()import java.util.HashMap;
import java.util.Scanner;
public class ElementCounter {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
HashMap<Integer, Integer> count = new HashMap<>();
System.out.print("Enter number of elements: ");
int n = scanner.nextInt();
System.out.println("Enter the elements:");
for (int i = 0; i < n; ++i) {
int x = scanner.nextInt();
count.put(x, count.getOrDefault(x, 0) + 1);
}
// Example query
System.out.print("Enter element to query: ");
int query = scanner.nextInt();
System.out.println("Element " + query + " appears " + count.getOrDefault(query, 0) + " times");
}
}#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
int n, x;
unordered_map<int, int> count;
cout << "Enter number of elements: ";
cin >> n;
cout << "Enter the elements:\n";
for (int i = 0; i < n; ++i) {
cin >> x;
count[x]++;
}
// Example query
cout << "Enter element to query: ";
cin >> x;
cout << "Element " << x << " appears " << count[x] << " times\n";
return 0;
}function elementCount() {
let count = {};
let n = parseInt(prompt("Enter number of elements:"));
console.log("Enter the elements:");
for (let i = 0; i < n; i++) {
let x = parseInt(prompt());
if (count[x]) {
count[x]++;
} else {
count[x] = 1;
}
}
// Example query
let query = parseInt(prompt("Enter element to query:"));
alert(`Element ${query} appears ${count[query] || 0} times`);
}
elementCount();#include <stdio.h>
#include <stdlib.h>
#define MAX 10000 // Adjust based on constraints
int main() {
int n, x;
printf("Enter number of elements: ");
scanf("%d", &n);
int count[MAX] = {0};
printf("Enter the elements (0 <= element < %d):\n", MAX);
for (int i = 0; i < n; i++) {
scanf("%d", &x);
count[x]++;
}
// Now, count contains the frequency of each element
// Example query
printf("Enter element to query: ");
scanf("%d", &x);
printf("Element %d appears %d times\n", x, count[x]);
return 0;
}using System;
using System.Collections.Generic;
class ElementCounter {
static void Main() {
Dictionary<int, int> count = new Dictionary<int, int>();
Console.Write("Enter number of elements: ");
int n = int.Parse(Console.ReadLine());
Console.WriteLine("Enter the elements:");
for (int i = 0; i < n; i++) {
int x = int.Parse(Console.ReadLine());
if (count.ContainsKey(x)) {
count[x]++;
} else {
count[x] = 1;
}
}
// Example query
Console.Write("Enter element to query: ");
int query = int.Parse(Console.ReadLine());
int result = count.ContainsKey(query) ? count[query] : 0;
Console.WriteLine($"Element {query} appears {result} times");
}
}This Python script uses a dictionary to count the frequency of elements. The dictionary is updated as elements are read, providing an efficient means to retrieve counts.
Time Complexity: O(n).
Space Complexity: O(m).
Approach 2: Approach 2: Sorting
By sorting the input list, elements of the same value will be grouped together. We can then iterate through the sorted list to count the occurrences of each element. This takes advantage of the property of sorting to simplify the counting process.
def sorted_element_count():
n = int(input("Enter number of elements: "))
arr = [int(input()) for _ in range(n)]
arr.sort() # In-place sort
print("Sorted elements for counting:")
current = arr[0]
count = 1
for i in range(1, n):
if arr[i] == current:
count += 1
else:
print(f"Element {current} appears {count} times")
current = arr[i]
count = 1
print(f"Element {current} appears {count} times")
sorted_element_count()import java.util.Arrays;
import java.util.Scanner;
public class SortedElementCounter {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("Enter number of elements: ");
int n = scanner.nextInt();
int[] arr = new int[n];
System.out.println("Enter the elements:");
for (int i = 0; i < n; ++i) {
arr[i] = scanner.nextInt();
}
Arrays.sort(arr);
System.out.println("Sorted elements for counting:");
int current = arr[0];
int count = 1;
for (int i = 1; i < n; ++i) {
if (arr[i] == current) {
count++;
} else {
System.out.println("Element " + current + " appears " + count + " times");
current = arr[i];
count = 1;
}
}
System.out.println("Element " + current + " appears " + count + " times");
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cout << "Enter number of elements: ";
cin >> n;
vector<int> arr(n);
cout << "Enter the elements:\n";
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
sort(arr.begin(), arr.end());
cout << "Sorted elements for counting:\n";
int current = arr[0];
int count = 1;
for (int i = 1; i < n; ++i) {
if (arr[i] == current) {
count++;
} else {
cout << "Element " << current << " appears " << count << " times\n";
current = arr[i];
count = 1;
}
}
cout << "Element " << current << " appears " << count << " times\n";
return 0;
}function sortedElementCount() {
let n = parseInt(prompt("Enter number of elements:"));
let arr = [];
console.log("Enter the elements:");
for (let i = 0; i < n; ++i) {
arr.push(parseInt(prompt()));
}
arr.sort((a, b) => a - b);
console.log("Sorted elements for counting:");
let current = arr[0];
let count = 1;
for (let i = 1; i < n; ++i) {
if (arr[i] === current) {
count++;
} else {
console.log(`Element ${current} appears ${count} times`);
current = arr[i];
count = 1;
}
}
console.log(`Element ${current} appears ${count} times`);
}
sortedElementCount();#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
int main() {
int n;
printf("Enter number of elements: ");
scanf("%d", &n);
int arr[n];
printf("Enter the elements:\n");
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
qsort(arr, n, sizeof(int), compare);
printf("Sorted elements for counting:\n");
int current = arr[0];
int count = 1;
for (int i = 1; i < n; i++) {
if (arr[i] == current) {
count++;
} else {
printf("Element %d appears %d times\n", current, count);
current = arr[i];
count = 1;
}
}
printf("Element %d appears %d times\n", current, count);
return 0;
}using System;
using System.Linq;
class SortedElementCounter {
static void Main() {
Console.Write("Enter number of elements: ");
int n = int.Parse(Console.ReadLine());
int[] arr = new int[n];
Console.WriteLine("Enter the elements:");
for (int i = 0; i < n; i++) {
arr[i] = int.Parse(Console.ReadLine());
}
Array.Sort(arr);
Console.WriteLine("Sorted elements for counting:");
int current = arr[0];
int count = 1;
for (int i = 1; i < n; i++) {
if (arr[i] == current) {
count++;
} else {
Console.WriteLine($"Element {current} appears {count} times");
current = arr[i];
count = 1;
}
}
Console.WriteLine($"Element {current} appears {count} times");
}
}Using Python's built-in sort() method, this script sorts elements, then iterates over the sorted list to count and print occurrences.
Time Complexity: O(n log n).
Space Complexity: O(1) additional space.
Approach 3: Sliding Window + Hash Table
We maintain a sliding window of length k, use a hash table cnt to record the count of each number in the window, and use a variable s to record the sum of all numbers in the window. Each time we slide the window, if all numbers in the window are unique, we update the answer.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.
function maximumSubarraySum(nums: number[], k: number): number {
const n = nums.length;
const cnt: Map<number, number> = new Map();
let s = 0;
for (let i = 0; i < k; ++i) {
cnt.set(nums[i], (cnt.get(nums[i]) ?? 0) + 1);
s += nums[i];
}
let ans = cnt.size === k ? s : 0;
for (let i = k; i < n; ++i) {
cnt.set(nums[i], (cnt.get(nums[i]) ?? 0) + 1);
cnt.set(nums[i - k], cnt.get(nums[i - k])! - 1);
if (cnt.get(nums[i - k]) === 0) {
cnt.delete(nums[i - k]);
}
s += nums[i] - nums[i - k];
if (cnt.size === k) {
ans = Math.max(ans, s);
}
}
return ans;
}func maximumSubarraySum(nums []int, k int) (ans int64) {
n := len(nums)
cnt := map[int]int64{}
var s int64
for _, x := range nums[:k] {
cnt[x]++
s += int64(x)
}
if len(cnt) == k {
ans = s
}
for i := k; i < n; i++ {
cnt[nums[i]]++
cnt[nums[i-k]]--
if cnt[nums[i-k]] == 0 {
delete(cnt, nums[i-k])
}
s += int64(nums[i] - nums[i-k])
if len(cnt) == k && ans < s {
ans = s
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Hash Map for Counting | Time Complexity: O(n). |
| Approach 2: Sorting | Time Complexity: O(n log n). |
| Sliding Window + Hash Table | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting each window | O(n log k) | O(k) | Simple baseline approach when optimizing is not required or for understanding the problem first |
| Hash Map + Sliding Window | O(n) | O(k) | Best general solution for large arrays where you must maintain a fixed window and enforce distinct elements |
Frequently asked questions
Is Maximum Sum of Distinct Subarrays With Length K easy or hard?
The problem is rated Medium because it combines two constraints: fixed window size and element uniqueness. Recognizing the sliding window pattern is straightforward, but correctly maintaining the frequency map and window sum requires careful implementation.
Maximum Sum of Distinct Subarrays With Length K Python/Java solution
Implement the sliding window approach with a dictionary or HashMap to track counts and a variable for the current window sum. Move the right pointer to add elements and shrink from the left when the window exceeds size k. When the window size is k and all elements are distinct, update the maximum sum. The same logic works in Python, Java, C++, and JavaScript with minor syntax differences.
How to solve Maximum Sum of Distinct Subarrays With Length K in O(n)?
Use a sliding window of size k and maintain a hash map that stores frequencies of elements in the current window. Keep a running sum of the window elements. When the window grows beyond k, remove the leftmost element and update both the sum and its frequency in the map. Whenever the window size equals k and the map size equals k, update the maximum sum.
What is the best approach for Maximum Sum of Distinct Subarrays With Length K?
The best approach uses a sliding window combined with a hash map to track element frequencies. As the window moves across the array, update the running sum and maintain counts in the map. When the window size equals k and the number of unique elements is also k, the subarray is valid. This method runs in O(n) time with O(k) extra space.
Is Maximum Sum of Distinct Subarrays With Length K asked at Google/Amazon/Meta?
Sliding window problems with uniqueness constraints frequently appear in interviews at companies like Amazon, Google, and Meta. Variants include longest substring with distinct characters or maximum sum subarray with constraints. This problem tests understanding of hash maps, window maintenance, and linear-time optimization.
What data structure is used in Maximum Sum of Distinct Subarrays With Length K?
A hash map (or dictionary) is used to store frequency counts of elements inside the current sliding window. This allows constant-time updates when elements enter or leave the window. The approach also maintains a running sum and two pointers representing the window boundaries.
What is the time complexity of Maximum Sum of Distinct Subarrays With Length K?
The optimal sliding window solution runs in O(n) time because each element enters and leaves the window at most once. Hash map updates and lookups are O(1) on average. The auxiliary space complexity is O(k) since the map stores at most k elements.