Description
You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists.
The depth of an integer is the number of lists that it is inside of. For example, the nested list [1,[2,2],[[3],2],1] has each integer's value set to its depth. Let maxDepth be the maximum depth of any integer.
The weight of an integer is maxDepth - (the depth of the integer) + 1.
Return the sum of each integer in nestedList multiplied by its weight.
Example 1:
Input: nestedList = [[1,1],2,[1,1]]
Output: 8
Explanation: Four 1's with a weight of 1, one 2 with a weight of 2.
1*1 + 1*1 + 2*2 + 1*1 + 1*1 = 8
Example 2:
Input: nestedList = [1,[4,[6]]]
Output: 17
Explanation: One 1 at depth 3, one 4 at depth 2, and one 6 at depth 1.
1*3 + 4*2 + 6*1 = 17
Constraints:
1 <= nestedList.length <= 50- The values of the integers in the nested list is in the range
[-100, 100].
- The maximum depth of any integer is less than or equal to
50.
- There are no empty lists.
Solutions
Solution 1: DFS
Let's assume the integers are a_1, a_2, …, a_n, their depths are d_1, d_2, …, d_n, the maximum depth is maxDepth, then the answer is:
$$
a_1 \times \textit{maxDepth} - a_1 \times d_1 + a_1 + a_2 \times \textit{maxDepth} - a_2 \times d_2 + a_2 + \cdots + a_n \times \textit{maxDepth} - a_n \times d_n + a_n
$$
which is:
$$
(\textit{maxDepth} + 1) \times (a_1 + a_2 + \cdots + a_n) - (a_1 \times d_1 + a_2 \times d_2 + \cdots + a_n \times d_n)
$$
If we denote the sum of all integers as s, and the sum of each integer multiplied by its depth as ws, then the answer is:
$$
(\textit{maxDepth} + 1) \times s - ws
$$
Therefore, we design a function dfs(x, d), which starts searching from x with depth d. The execution process of dfs(x, d) is as follows:
- We first update maxDepth = max(maxDepth, d);
- If x is an integer, then we update s = s + x, ws = ws + x × d;
- Otherwise, we recursively traverse each element y of x, and call dfs(y, d + 1).
We traverse the entire list, for each element x, we call dfs(x, 1), and finally return (maxDepth + 1) × s - ws.
The time complexity is O(n), and the space complexity is O(n). Where n is the number of integers.
PythonJavaC++GoTypeScriptJavaScript
# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
# class NestedInteger:
# def __init__(self, value=None):
# """
# If value is not specified, initializes an empty list.
# Otherwise initializes a single integer equal to value.
# """
#
# def isInteger(self):
# """
# @return True if this NestedInteger holds a single integer, rather than a nested list.
# :rtype bool
# """
#
# def add(self, elem):
# """
# Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
# :rtype void
# """
#
# def setInteger(self, value):
# """
# Set this NestedInteger to hold a single integer equal to value.
# :rtype void
# """
#
# def getInteger(self):
# """
# @return the single integer that this NestedInteger holds, if it holds a single integer
# Return None if this NestedInteger holds a nested list
# :rtype int
# """
#
# def getList(self):
# """
# @return the nested list that this NestedInteger holds, if it holds a nested list
# Return None if this NestedInteger holds a single integer
# :rtype List[NestedInteger]
# """
class Solution:
def depthSumInverse(self, nestedList: List[NestedInteger]) -> int:
def dfs(x, d):
nonlocal maxDepth, s, ws
maxDepth = max(maxDepth, d)
if x.isInteger():
s += x.getInteger()
ws += x.getInteger() * d
else:
for y in x.getList():
dfs(y, d + 1)
maxDepth = s = ws = 0
for x in nestedList:
dfs(x, 1)
return (maxDepth + 1) * s - ws(code-box)
/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* public interface NestedInteger {
* // Constructor initializes an empty nested list.
* public NestedInteger();
*
* // Constructor initializes a single integer.
* public NestedInteger(int value);
*
* // @return true if this NestedInteger holds a single integer, rather than a nested list.
* public boolean isInteger();
*
* // @return the single integer that this NestedInteger holds, if it holds a single integer
* // Return null if this NestedInteger holds a nested list
* public Integer getInteger();
*
* // Set this NestedInteger to hold a single integer.
* public void setInteger(int value);
*
* // Set this NestedInteger to hold a nested list and adds a nested integer to it.
* public void add(NestedInteger ni);
*
* // @return the nested list that this NestedInteger holds, if it holds a nested list
* // Return empty list if this NestedInteger holds a single integer
* public List<NestedInteger> getList();
* }
*/
class Solution {
private int maxDepth;
private int ws;
private int s;
public int depthSumInverse(List<NestedInteger> nestedList) {
for (NestedInteger x : nestedList) {
dfs(x, 1);
}
return (maxDepth + 1) * s - ws;
}
private void dfs(NestedInteger x, int d) {
maxDepth = Math.max(maxDepth, d);
if (x.isInteger()) {
ws += x.getInteger() * d;
s += x.getInteger();
} else {
for (NestedInteger y : x.getList()) {
dfs(y, d + 1);
}
}
}
}(code-box)
/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* class NestedInteger {
* public:
* // Constructor initializes an empty nested list.
* NestedInteger();
*
* // Constructor initializes a single integer.
* NestedInteger(int value);
*
* // Return true if this NestedInteger holds a single integer, rather than a nested list.
* bool isInteger() const;
*
* // Return the single integer that this NestedInteger holds, if it holds a single integer
* // The result is undefined if this NestedInteger holds a nested list
* int getInteger() const;
*
* // Set this NestedInteger to hold a single integer.
* void setInteger(int value);
*
* // Set this NestedInteger to hold a nested list and adds a nested integer to it.
* void add(const NestedInteger &ni);
*
* // Return the nested list that this NestedInteger holds, if it holds a nested list
* // The result is undefined if this NestedInteger holds a single integer
* const vector<NestedInteger> &getList() const;
* };
*/
class Solution {
public:
int depthSumInverse(vector<NestedInteger>& nestedList) {
int maxDepth = 0, ws = 0, s = 0;
function<void(NestedInteger&, int)> dfs = [&](NestedInteger& x, int d) {
maxDepth = max(maxDepth, d);
if (x.isInteger()) {
ws += x.getInteger() * d;
s += x.getInteger();
} else {
for (auto& y : x.getList()) {
dfs(y, d + 1);
}
}
};
for (auto& x : nestedList) {
dfs(x, 1);
}
return (maxDepth + 1) * s - ws;
}
};(code-box)
/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* type NestedInteger struct {
* }
*
* // Return true if this NestedInteger holds a single integer, rather than a nested list.
* func (n NestedInteger) IsInteger() bool {}
*
* // Return the single integer that this NestedInteger holds, if it holds a single integer
* // The result is undefined if this NestedInteger holds a nested list
* // So before calling this method, you should have a check
* func (n NestedInteger) GetInteger() int {}
*
* // Set this NestedInteger to hold a single integer.
* func (n *NestedInteger) SetInteger(value int) {}
*
* // Set this NestedInteger to hold a nested list and adds a nested integer to it.
* func (n *NestedInteger) Add(elem NestedInteger) {}
*
* // Return the nested list that this NestedInteger holds, if it holds a nested list
* // The list length is zero if this NestedInteger holds a single integer
* // You can access NestedInteger's List element directly if you want to modify it
* func (n NestedInteger) GetList() []*NestedInteger {}
*/
func depthSumInverse(nestedList []*NestedInteger) int {
var maxDepth, ws, s int
var dfs func(*NestedInteger, int)
dfs = func(x *NestedInteger, d int) {
maxDepth = max(maxDepth, d)
if x.IsInteger() {
ws += x.GetInteger() * d
s += x.GetInteger()
} else {
for _, y := range x.GetList() {
dfs(y, d+1)
}
}
}
for _, x := range nestedList {
dfs(x, 1)
}
return (maxDepth+1)*s - ws
}(code-box)
/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* class NestedInteger {
* If value is provided, then it holds a single integer
* Otherwise it holds an empty nested list
* constructor(value?: number) {
* ...
* };
*
* Return true if this NestedInteger holds a single integer, rather than a nested list.
* isInteger(): boolean {
* ...
* };
*
* Return the single integer that this NestedInteger holds, if it holds a single integer
* Return null if this NestedInteger holds a nested list
* getInteger(): number | null {
* ...
* };
*
* Set this NestedInteger to hold a single integer equal to value.
* setInteger(value: number) {
* ...
* };
*
* Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
* add(elem: NestedInteger) {
* ...
* };
*
* Return the nested list that this NestedInteger holds,
* or an empty list if this NestedInteger holds a single integer
* getList(): NestedInteger[] {
* ...
* };
* };
*/
function depthSumInverse(nestedList: NestedInteger[]): number {
let [maxDepth, ws, s] = [0, 0, 0];
const dfs = (x: NestedInteger, d: number) => {
maxDepth = Math.max(maxDepth, d);
if (x.isInteger()) {
ws += x.getInteger() * d;
s += x.getInteger();
} else {
for (const y of x.getList()) {
dfs(y, d + 1);
}
}
};
for (const x of nestedList) {
dfs(x, 1);
}
return (maxDepth + 1) * s - ws;
}(code-box)
/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* function NestedInteger() {
*
* Return true if this NestedInteger holds a single integer, rather than a nested list.
* @return {boolean}
* this.isInteger = function() {
* ...
* };
*
* Return the single integer that this NestedInteger holds, if it holds a single integer
* Return null if this NestedInteger holds a nested list
* @return {integer}
* this.getInteger = function() {
* ...
* };
*
* Set this NestedInteger to hold a single integer equal to value.
* @return {void}
* this.setInteger = function(value) {
* ...
* };
*
* Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
* @return {void}
* this.add = function(elem) {
* ...
* };
*
* Return the nested list that this NestedInteger holds, if it holds a nested list
* Return null if this NestedInteger holds a single integer
* @return {NestedInteger[]}
* this.getList = function() {
* ...
* };
* };
*/
/**
* @param {NestedInteger[]} nestedList
* @return {number}
*/
var depthSumInverse = function (nestedList) {
let [maxDepth, ws, s] = [0, 0, 0];
const dfs = (x, d) => {
maxDepth = Math.max(maxDepth, d);
if (x.isInteger()) {
ws += x.getInteger() * d;
s += x.getInteger();
} else {
for (const y of x.getList()) {
dfs(y, d + 1);
}
}
};
for (const x of nestedList) {
dfs(x, 1);
}
return (maxDepth + 1) * s - ws;
};(code-box)
