What is the time complexity of the solution for the distinct difference array?

The time complexity of the optimal solution is O(n), where n is the length of the input array. This is achieved by using hash sets to count distinct elements in the prefix and suffix while iterating through the array once.

How can I optimize space complexity in the distinct difference array problem?

Space complexity can be optimized by using hash sets for the prefix and suffix, ensuring that the distinct element counts are tracked in constant space relative to the array's size.

What pattern should I use to solve the Find the Distinct Difference Array problem?

The primary pattern is array scanning combined with hash lookups, where hash sets efficiently track distinct elements in both the prefix and suffix of the array.

What is the distinct difference array in this problem?

The distinct difference array is an array where each element diff[i] represents the difference between the distinct elements in the prefix nums[0...i] and the distinct elements in the suffix nums[i+1...n-1].

What should I focus on when solving the Find the Distinct Difference Array problem?

Focus on efficiently counting distinct elements using hash sets, iterating over the array in linear time while ensuring the correct update of distinct counts for both prefix and suffix.

#2670

Easy

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

找出不同元素数目差数组

给你一个下标从 0 开始的数组 nums ，数组长度为 n 。 nums 的不同元素数目差数组可以用一个长度为 n 的数组 diff 表示，其中 diff[i] 等于前缀 nums[0, ..., i] 中不同元素的数目减去后缀 nums[i + 1, ..., n - 1] 中不同元素的数…

数组哈希表

题目描述

给你一个下标从 0 开始的数组 nums ，数组长度为 n 。

nums 的 不同元素数目差 数组可以用一个长度为 n 的数组 diff 表示，其中 diff[i] 等于前缀 nums[0, ..., i] 中不同元素的数目减去后缀 nums[i + 1, ..., n - 1] 中不同元素的数目。

返回 nums 的 不同元素数目差 数组。

注意 nums[i, ..., j] 表示 nums 的一个从下标 i 开始到下标 j 结束的子数组（包含下标 i 和 j 对应元素）。特别需要说明的是，如果 i > j ，则 nums[i, ..., j] 表示一个空子数组。

示例 1：

输入：nums = [1,2,3,4,5]
输出：[-3,-1,1,3,5]
解释：
对于 i = 0，前缀中有 1 个不同的元素，而在后缀中有 4 个不同的元素。因此，diff[0] = 1 - 4 = -3 。
对于 i = 1，前缀中有 2 个不同的元素，而在后缀中有 3 个不同的元素。因此，diff[1] = 2 - 3 = -1 。
对于 i = 2，前缀中有 3 个不同的元素，而在后缀中有 2 个不同的元素。因此，diff[2] = 3 - 2 = 1 。
对于 i = 3，前缀中有 4 个不同的元素，而在后缀中有 1 个不同的元素。因此，diff[3] = 4 - 1 = 3 。
对于 i = 4，前缀中有 5 个不同的元素，而在后缀中有 0 个不同的元素。因此，diff[4] = 5 - 0 = 5 。

示例 2：

输入：nums = [3,2,3,4,2]
输出：[-2,-1,0,2,3]
解释：
对于 i = 0，前缀中有 1 个不同的元素，而在后缀中有 3 个不同的元素。因此，diff[0] = 1 - 3 = -2 。
对于 i = 1，前缀中有 2 个不同的元素，而在后缀中有 3 个不同的元素。因此，diff[1] = 2 - 3 = -1 。
对于 i = 2，前缀中有 2 个不同的元素，而在后缀中有 2 个不同的元素。因此，diff[2] = 2 - 2 = 0 。
对于 i = 3，前缀中有 3 个不同的元素，而在后缀中有 1 个不同的元素。因此，diff[3] = 3 - 1 = 2 。
对于 i = 4，前缀中有 3 个不同的元素，而在后缀中有 0 个不同的元素。因此，diff[4] = 3 - 0 = 3 。

提示：

1 <= n == nums.length <= 50
1 <= nums[i] <= 50

lightbulb

解题思路

方法一：哈希表 + 预处理后缀

我们可以预处理出一个后缀数组 $suf$ ，其中 $suf[i]$ 表示后缀 $nums[i, ..., n - 1]$ 中不同元素的数目，在预处理过程中，我们使用一个哈希表 $s$ 来维护后缀中出现过的元素，这样我们就可以在 $O(1)$ 的时间内查询后缀中不同元素的数目。

预处理完后缀数组 $suf$ 后，我们清空哈希表 $s$ ，然后再次遍历数组 $nums$ ，用哈希表 $s$ 来维护前缀中出现过的元素，那么位置 $i$ 的答案就是 $s$ 中不同元素的数目减去 $suf[i + 1]$ ，即 $|s| - suf[i + 1]$ 。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是数组 $nums$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:
        n = len(nums)
        suf = [0] * (n + 1)
        s = set()
        for i in range(n - 1, -1, -1):
            s.add(nums[i])
            suf[i] = len(s)
        s.clear()
        ans = [0] * n
        for i, x in enumerate(nums):
            s.add(x)
            ans[i] = len(s) - suf[i + 1]
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Focus on how efficiently you can update distinct counts in both prefix and suffix.
question_mark
Watch for candidates who may attempt brute force methods like nested loops that result in O(n^2) time complexity.
question_mark
Evaluate the candidate's approach to optimizing space usage, especially when dealing with hash sets.

warning

常见陷阱

外企场景

error
Using nested loops for counting distinct elements leads to inefficient O(n^2) time complexity.
error
Not updating the suffix count correctly while iterating through the array.
error
Forgetting to handle the case where there are no elements in the suffix for the last element.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to find the distinct difference array for subarrays of different lengths.
arrow_right_alt
Allow negative numbers in the array and handle distinct counting for negative values.
arrow_right_alt
Increase the array size limit and evaluate performance under larger inputs.

help

常见问题

外企场景

继续练习

#2661 找出叠涂元素 #2682 找出转圈游戏输家 #2657 找到两个数组的前缀公共数组