2763. Sum of Imbalance Numbers of All Subarrays LeetCode Solution
In this guide, you will get 2763. Sum of Imbalance Numbers of All Subarrays LeetCode Solution with the best time and space complexity. The solution to Sum of Imbalance Numbers of All Subarrays problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Sum of Imbalance Numbers of All Subarrays
The imbalance number of a 0-indexed integer array arr of length n is defined as the number of indices in sarr = sorted(arr) such that:
0 <= i 1
Here, sorted(arr) is the function that returns the sorted version of arr.
Given a 0-indexed integer array nums, return the sum of imbalance numbers of all its subarrays.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [2,3,1,4]
Output: 3
Explanation: There are 3 subarrays with non-zero imbalance numbers:
– Subarray [3, 1] with an imbalance number of 1.
– Subarray [3, 1, 4] with an imbalance number of 1.
– Subarray [1, 4] with an imbalance number of 1.
The imbalance number of all other subarrays is 0. Hence, the sum of imbalance numbers of all the subarrays of nums is 3.
Example 2:
Input: nums = [1,3,3,3,5]
Output: 8
Explanation: There are 7 subarrays with non-zero imbalance numbers:
– Subarray [1, 3] with an imbalance number of 1.
– Subarray [1, 3, 3] with an imbalance number of 1.
– Subarray [1, 3, 3, 3] with an imbalance number of 1.
– Subarray [1, 3, 3, 3, 5] with an imbalance number of 2.
– Subarray [3, 3, 3, 5] with an imbalance number of 1.
– Subarray [3, 3, 5] with an imbalance number of 1.
– Subarray [3, 5] with an imbalance number of 1.
The imbalance number of all other subarrays is 0. Hence, the sum of imbalance numbers of all the subarrays of nums is 8.
2763. Sum of Imbalance Numbers of All Subarrays LeetCode Solution in C++
class Solution {
public:
// If sorted(nums)[i + 1] - sorted(nums)[i] > 1, then there's a gap. Instead
// of determining the number of gaps in each subarray, let's find out how many
// subarrays contain each gap.
int sumImbalanceNumbers(vector<int>& nums) {
const int n = nums.size();
int ans = 0;
// Note that to avoid double counting, only `left` needs to check nums[i].
// This adjustment ensures that i represents the position of the leftmost
// element of nums[i] within the subarray.
// left[i] := the maximum index l s.t. nums[l] = nums[i] or nums[i] + 1
vector<int> left(n);
// right[i] := the minimum index r s.t. nums[r] = nums[i]
vector<int> right(n);
vector<int> numToIndex(n + 2, -1);
for (int i = 0; i < n; ++i) {
left[i] = max(numToIndex[nums[i]], numToIndex[nums[i] + 1]);
numToIndex[nums[i]] = i;
}
fill(numToIndex.begin(), numToIndex.end(), n);
for (int i = n - 1; i >= 0; --i) {
right[i] = numToIndex[nums[i] + 1];
numToIndex[nums[i]] = i;
}
// The gap above nums[i] persists until encountering nums[i] or nums[i] + 1.
// Consider subarrays nums[l..r] with l <= i <= r, where l in [left[i], i]
// and r in [i, right[i] - 1]. There are (i - left[i]) * (right[i] - i)
// subarrays satisfying this condition.
for (int i = 0; i < n; ++i)
ans += (i - left[i]) * (right[i] - i);
// Subtract n * (n + 1) / 2 to account for the overcounting of elements
// initially assumed to have a gap. This adjustment is necessary as the
// maximum element of every subarray does not have a gap.
return ans - n * (n + 1) / 2;
}
}; /* code provided by PROGIEZ */
2763. Sum of Imbalance Numbers of All Subarrays LeetCode Solution in Java
class Solution {
// If sorted(nums)[i + 1] - sorted(nums)[i] > 1, then there's a gap. Instead
// of determining the number of gaps in each subarray, let's find out how many
// subarrays contain each gap.
public int sumImbalanceNumbers(int[] nums) {
final int n = nums.length;
int ans = 0;
// Note that to avoid double counting, only `left` needs to check nums[i].
// This adjustment ensures that i represents the position of the leftmost
// element of nums[i] within the subarray.
// left[i] := the maximum index l s.t. nums[l] = nums[i] or nums[i] + 1
int[] left = new int[n];
// right[i] := the minimum index r s.t. nums[r] = nums[i]
int[] right = new int[n];
int[] numToIndex = new int[n + 2];
Arrays.fill(numToIndex, -1);
for (int i = 0; i < n; ++i) {
left[i] = Math.max(numToIndex[nums[i]], numToIndex[nums[i] + 1]);
numToIndex[nums[i]] = i;
}
Arrays.fill(numToIndex, n);
for (int i = n - 1; i >= 0; --i) {
right[i] = numToIndex[nums[i] + 1];
numToIndex[nums[i]] = i;
}
// The gap above nums[i] persists until encountering nums[i] or nums[i] + 1.
// Consider subarrays nums[l..r] with l <= i <= r, where l in [left[i], i]
// and r in [i, right[i] - 1]. There are (i - left[i]) * (right[i] - i)
// subarrays satisfying this condition.
for (int i = 0; i < n; ++i)
ans += (i - left[i]) * (right[i] - i);
// Subtract n * (n + 1) / 2 to account for the overcounting of elements
// initially assumed to have a gap. This adjustment is necessary as the
// maximum element of every subarray does not have a gap.
return ans - n * (n + 1) / 2;
}
} // code provided by PROGIEZ
2763. Sum of Imbalance Numbers of All Subarrays LeetCode Solution in Python
class Solution:
# If sorted(nums)[i + 1] - sorted(nums)[i] > 1, then there's a gap. Instead
# of determining the number of gaps in each subarray, let's find out how many
# subarrays contain each gap.
def sumImbalanceNumbers(self, nums: list[int]) -> int:
n = len(nums)
# Note that to avoid double counting, only `left` needs to check nums[i].
# This adjustment ensures that i represents the position of the leftmost
# element of nums[i] within the subarray.
# left[i] := the maximum index l s.t. nums[l] = nums[i] or nums[i] + 1
left = [0] * n
# right[i] := the minimum index r s.t. nums[r] = nums[i]
right = [0] * n
numToIndex = [-1] * (n + 2)
for i, num in enumerate(nums):
left[i] = max(numToIndex[num], numToIndex[num + 1])
numToIndex[num] = i
numToIndex = [n] * (n + 2)
for i in range(n - 1, -1, -1):
right[i] = numToIndex[nums[i] + 1]
numToIndex[nums[i]] = i
# The gap above nums[i] persists until encountering nums[i] or nums[i] + 1.
# Consider subarrays nums[l..r] with l <= i <= r, where l in [left[i], i]
# and r in [i, right[i] - 1]. There are (i - left[i]) * (right[i] - i)
# subarrays satisfying this condition.
#
# Subtract n * (n + 1) / 2 to account for the overcounting of elements
# initially assumed to have a gap. This adjustment is necessary as the
# maximum element of every subarray does not have a gap.
return sum((i - left[i]) * (right[i] - i)
for i in range(n)) - n * (n + 1) // 2 # code by PROGIEZ
