Subarrays Distinct Element Sum of Squares II - Video Solutions

HardArrayDynamic ProgrammingBinary Indexed TreeSegment Tree

LeetCode was HARD until I Learned these 15 Patterns

13:001,002,273 views

10 video solutions available

Subarrays Distinct Element Sum of Squares II - Video Solution

Watch 10 video solutions for Subarrays Distinct Element Sum of Squares II, a hard level problem involving Array, Dynamic Programming, Binary Indexed Tree. This walkthrough by Ashish Pratap Singh has 1,002,273 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.

Problem Statement

You are given a 0-indexed integer array nums.

The distinct count of a subarray of nums is defined as:

Let nums[i..j] be a subarray of nums consisting of all the indices from i to j such that 0 <= i <= j < nums.length. Then the number of distinct values in nums[i..j] is called the distinct count of nums[i..j].

Return the sum of the squares of distinct counts of all subarrays of nums.

Since the answer may be very large, return it modulo 10⁹ + 7.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [1,2,1]
Output: 15
Explanation: Six possible subarrays are:
[1]: 1 distinct value
[2]: 1 distinct value
[1]: 1 distinct value
[1,2]: 2 distinct values
[2,1]: 2 distinct values
[1,2,1]: 2 distinct values
The sum of the squares of the distinct counts in all subarrays is equal to 1² + 1² + 1² + 2² + 2² + 2² = 15.

Example 2:

Input: nums = [2,2]
Output: 3
Explanation: Three possible subarrays are:
[2]: 1 distinct value
[2]: 1 distinct value
[2,2]: 1 distinct value
The sum of the squares of the distinct counts in all subarrays is equal to 1² + 1² + 1² = 3.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵

Read full problem with examples

Continue Learning

Practice this problem

Solve it on FleetCode

Read Solution & Explanation

Detailed text walkthrough

Subarrays Distinct Element Sum of Squares II - Video Solutions

LeetCode was HARD until I Learned these 15 Patterns

This is the Most Asked FAANG Interview Question! - Two Sum - Leetcode 1

Subarray Sum Equals K - Prefix Sums - Leetcode 560 - Python

Two Sum II - Two Pointers Algorithm - Leetcode 167

Maximum Sum of Distinct Subarrays With Length K - Leetcode 2461 - Python

Beautiful Segment tree lazy idea | Subarrays Distinct Element Sum of Squares II

2916. Subarrays Distinct Element Sum of Squares II | 2913 | Leetcode Biweekly 116

Subarrays Distinct Element Sum of Squares I |Biweekly Contest 116 | Leetcode | DCC NIT-A

2913. Subarrays Distinct Element Sum of Squares I (Leetcode Easy)

2916. Subarrays Distinct Element Sum of Squares II (Leetcode Hard)

Subarrays Distinct Element Sum of Squares II - Video Solution

Problem Statement

Continue Learning

Subarrays Distinct Element Sum of Squares II - Video Solutions

LeetCode was HARD until I Learned these 15 Patterns

This is the Most Asked FAANG Interview Question! - Two Sum - Leetcode 1

Subarray Sum Equals K - Prefix Sums - Leetcode 560 - Python

Two Sum II - Two Pointers Algorithm - Leetcode 167

Maximum Sum of Distinct Subarrays With Length K - Leetcode 2461 - Python

Beautiful Segment tree lazy idea | Subarrays Distinct Element Sum of Squares II

2916. Subarrays Distinct Element Sum of Squares II | 2913 | Leetcode Biweekly 116

Subarrays Distinct Element Sum of Squares I |Biweekly Contest 116 | Leetcode | DCC NIT-A

2913. Subarrays Distinct Element Sum of Squares I (Leetcode Easy)

2916. Subarrays Distinct Element Sum of Squares II (Leetcode Hard)

Subarrays Distinct Element Sum of Squares II - Video Solution

Problem Statement

Continue Learning