[LeetCode] 430. Flatten a Multilevel Doubly Linked List

 Problem : https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/

 Use stack to mimic DFS

"""
# Definition for a Node.
class Node:
    def __init__(self, val, prev, next, child):
        self.val = val
        self.prev = prev
        self.next = next
        self.child = child
"""

class Solution:
    def flatten(self, head: 'Node') -> 'Node':
        if not head: return None
        
        dummy = Node()
        p = dummy
        
        stack = [head]
        
        while stack:
            h = stack.pop()
            
            while h:
                p.next = h
                h.prev = p
                p = p.next
                    
                if h.child:
                    if h.next:
                        stack.append(h.next)
                    
                    tmp = h.child
                    h.child = None
                    h = tmp
                else:
                    h = h.next
                
        
        dummy.next.prev = None
        return dummy.next

[LeetCode] 1059. All Paths from Source Lead to Destination

 Problem: https://leetcode.com/problems/all-paths-from-source-lead-to-destination/

We need to check if all paths start from 'source' can end up with the 'destination' and there is no cycle exists on the paths.

class Solution:
    def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        graph = defaultdict(set)
        
        for a, b in edges:
            graph[a].add(b)
            
        def dfs(a, visited):
            if a in visited:
                # detect a cycle
                return False
            
            if not graph[a]:
                # check if it ends up at 'destination'
                return a == destination
            
            visited.add(a)
            
            for b in graph[a]:
                if not dfs(b, visited):
                    return False
            
            visited.remove(a)
            return True
        
        return dfs(source, set())

[LeetCode] 1161. Maximum Level Sum of a Binary Tree

 Problem : https://leetcode.com/problems/maximum-level-sum-of-a-binary-tree/

This is an easy problem which can be solved by either DFS or BFS.

But it needs to be aware that because node may have negative value, we cannot determine the final sum of a level until traversal is completed. 

Time Complexity = O (N + N)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxLevelSum(self, root: Optional[TreeNode]) -> int:
        levels = []
        stack = [(root, 0)]
        
        while stack:
            node, index = stack.pop()
            
            if index == len(levels):
                levels.append(node.val)
            else:
                levels[index] += node.val
 
            if node.right:
                stack.append((node.right, index + 1))
            if node.left:
                stack.append((node.left, index + 1))
        
        mxSoFar = levels[0]
        miLevel = 0
        
        for level, sums in enumerate(levels):
            if sums > mxSoFar:
                mxSoFar = sums
                miLevel = level
        
        return miLevel + 1

[LeetCode] 1448. Count Good Nodes in Binary Tree

 Problem : https://leetcode.com/problems/count-good-nodes-in-binary-tree/

Use DFS to find number of nodes where value not less than the current local maximum value.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        
        result = 0
        stack = [(root, -10**4)]
        
        while stack:
            node, mx = stack.pop()
            
            if mx <= node.val:
                result += 1
                mx = node.val
            
            if node.right:
                stack.append((node.right, mx))
            
            if node.left:
                stack.append((node.left, mx))
        
        return result

[LeetCode] 429. N-ary Tree Level Order Traversal

 Problem : https://leetcode.com/problems/n-ary-tree-level-order-traversal/

BFS Solution:

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        if not root: return []
        
        queue = [root]
        result = []
        
        while queue:
            result.append([node.val for node in queue])
            queue = [child for node in queue for child in node.children]
        
        return result

DFS Solution:

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        if not root: return []
        
        result = []
        
        stack = [(root, 0)]
        
        while stack:
            node, level = stack.pop()
            
            if level == len(result):
                result.append([node.val])
            else:
                result[level].append(node.val)
            
            for child in reversed(node.children):
                stack.append((child, level+1))
        
        return result

[LeetCode] 863. All Nodes Distance K in Binary Tree

 Problem : https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/

It is straightforward  to use BFS to collect the nodes on distance K in the binary tree. 

To support move upward and downward simultaneously, we need to add one more pointer to point from each node to its parent node. So we convert the given binary tree to a directed graph. 

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
        
        # use dfs to find parent of each nodes
        parent = {root: None}
        def dfs(node):
            for child in [node.left, node.right]:
                if child:
                    parent[child] = node
                    dfs(child)
        
        dfs(root)
        
        # start from target node and use bfs to find all nodes on distance k
        queue = deque([target])
        visited = set([target])
        
        result = []
        step = 0
        
        while queue and step <= k:
            for _ in range(len(queue)):
                node = queue.popleft()
                if step == k:
                    result.append(node.val)
                
                for nxt in [node.left, node.right, parent[node]]:
                    if nxt and nxt not in visited:
                        visited.add(nxt)
                        queue.append(nxt)
                
            step += 1
                
        return result

[LeetCode] 261. Graph Valid Tree

 Problem: https://leetcode.com/problems/graph-valid-tree/

Use DFS to locate if all nodes are connected and no loop exists.

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        
        seen = [False] * n
        visited = 0
        stack = [0]
        
        graph = defaultdict(set)
        
        for a, b in edges:
            graph[a].add(b)
            graph[b].add(a)
        
        while stack:
            a = stack.pop()
            
            if seen[a]:
                return False
            
            visited += 1
            seen[a] = True
            
            for b in graph[a]:
                stack.append(b)
                graph[b].remove(a)
            
        
        return visited == n

[LeetCode] 323. Number of Connected Components in an Undirected Graph

 Problem : https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/

Use DFS to find all connected nodes.

A stack based DFS solution:

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        
        graph = defaultdict(list)
        
        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)
                    
        result = 0
        seen = set()
        stack = []
        
        for i in range(n):
            if i not in seen:
                result += 1
                
                seen.add(i)
                stack.append(i)
                
                while stack:
                    a = stack.pop()
                    
                    for b in graph[a]:
                        if b not in seen:
                            seen.add(b)
                            stack.append(b)
        
        return result

[LeetCode] 666. Path Sum IV

 Problem : https://leetcode.com/problems/path-sum-iv/

Reconstruct the tree and them use DFS to get the path sums.

Because index starts from 1, for node coordinate (y, x):

-  left child coordinate on next level =  (y + 1,  2 * x - 1)

- right child coordinate on next level = (y + 1,  2 * x)

class Solution:
    def pathSum(self, nums: List[int]) -> int:
        
        tree = {}
        
        for n in nums:
            y = n // 100
            n = n % 100
            x = n // 10
            n = n % 10
            tree[(y, x)] = n
            
        
        def dfs(y, x, sums):
            if (y, x) in tree:
                sums += tree[(y,x)]
                
                # since index starts from 1
                # left child coordination = (y+1, 2*x - 1)
                # right child coordination = (y+1, 2*x)
                if (y+1, 2*x - 1) not in tree and (y+1, 2*x) not in tree:
                    yield sums
                else:
                    yield from dfs(y+1, 2*x-1, sums)
                    yield from dfs(y+1, 2*x, sums)
        
        
        return sum(dfs(1, 1, 0))    
        

[LeetCode] 437. Path Sum III

 Problem : https://leetcode.com/problems/path-sum-iii/

Traval tree in preorder approach. And use prefix-sum to find number of sub-array node value can form the target sum.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> int:
        self.result = 0
        
        
        def dfs(node, preSum, seen):
            if node:
                preSum += node.val
                self.result += seen[preSum - targetSum]
                
                seen[preSum] += 1
                
                dfs(node.left, preSum, seen)
                dfs(node.right, preSum, seen)
                    
                seen[preSum] -= 1
        
        
        seen = defaultdict(int)
        seen[0] = 1
        dfs(root, 0, seen)
        return self.result

[LeetCode] 337. House Robber III

 Problem : https://leetcode.com/problems/house-robber-iii/

Each level of the tree has 2 state :   safe or  not-safe.

If current level is safe to rob, thief can choose rob current level then next level is not safe to rob. Or skip current level, then next level is safe to rob.

Use memorization approach to find the answer.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rob(self, root: TreeNode) -> int:
        
        @lru_cache(maxsize = None)
        def helper(node, safe):
            result = 0
            
            if node:
                if safe:
                    result = node.val + helper(node.left, not safe) + helper(node.right, not safe)
                    result = max(result, helper(node.left, safe) + helper(node.right, safe))
                else:
                    result = helper(node.left, not safe) + helper(node.right, not safe)
                
            return result
        
        return max(helper(root, True), helper(root, False))

[LeetCode] 332. Reconstruct Itinerary

 Problem : https://leetcode.com/problems/reconstruct-itinerary/

Consider each city is a vertex in a directed graph, then every ticket is an edge between 2 vertices.

Use one hash table to track all available tickets. ( Notice : There could be duplicated tickets between 2 cities )

Then use DFS to find the possible path between city "JFK" to the ending city.

DFS ends when number of city = total number of tickets  + 1

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        graph = defaultdict(list)
        allTickets = defaultdict(int)
        
        for src, dst in tickets:
            graph[src].append(dst)
            allTickets[(src,dst)] += 1
        
        for src in graph.keys():
            graph[src].sort()
        
        
        def dfs(src, path):
            if len(path) == len(tickets) + 1:
                return path
            
            for dst in graph[src]:
                if allTickets[(src,dst)] > 0:
                    allTickets[(src,dst)] -= 1
                    
                    tmp = dfs(dst, path + [dst])
                    if tmp:
                        return tmp
                    
                    allTickets[(src,dst)] += 1
                    
            return None
        
    
        return dfs("JFK", ["JFK"])

[LeetCode] 306. Additive Number

 Problem : https://leetcode.com/problems/additive-number/

Use DFS approach to verify the sequence.

Time Complexity = O ( N ** 3 )

class Solution:
    def isAdditiveNumber(self, num: str) -> bool:
        def dfs(start, pre, target):
            if start == len(num):
                return True
            
            if num[start] == '0':
                if target == 0:
                    return dfs(start + 1, 0, 0)
                else:
                    return False
            
            for i in range(start+1, len(num) + 1):
                if int(num[start:i]) > target:
                    return False
                
                
                if int(num[start:i]) == target:
                    return dfs(i, target, pre + target)
            
            return False
        
        
        for i in range(1, len(num) - 1):
            for j in range(i+1, len(num)):
                if i > 1 and num[0] == '0':
                    break
                
                a = int(num[:i])
                
                if j - i > 1 and num[i] == '0':
                    continue
                    
                b = int(num[i:j])
                if dfs(j, b, a + b):
                    return True
        
        return False

[LeetCode] 301. Remove Invalid Parentheses

 Problem : https://leetcode.com/problems/remove-invalid-parentheses/

Iterating the input string from left right,  for each bracket, we have 2 options. Either keep this bracket or remove this bracket from the final expression. In the end, check the expression is valid by verify if opening bracket == closing bracket. Use removedCount to track how many bracket be removed from the final expression.  Only save the expression with minimal removal count.

Time Complexity = O ( 2 ** N ).     ( As for each character we can choose either keep or remove it from the final expression. )

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        self.result = set()
        self.minRemoved = 2 ** 31 - 1
        
        def helper(index, leftCount, rightCount, expression, removedCount):
            
            if index == len(s):
                if leftCount == rightCount:
                    if removedCount < self.minRemoved:
                        self.result = set([expression])
                        self.minRemoved = removedCount
                    elif removedCount == self.minRemoved:
                        self.result.add(expression)
            else:
                if s[index] not in '()':
                    helper(index + 1, leftCount, rightCount, expression + s[index], removedCount)
                else:
                    # remove this bracket
                    helper(index + 1, leftCount, rightCount, expression, removedCount + 1)
                    
                    # keep this bracket
                    if s[index] == '(':
                        helper(index + 1, leftCount + 1, rightCount, expression + s[index], removedCount)
                    elif rightCount < leftCount:
                        # only keep closing bracket when right < left
                        helper(index + 1, leftCount, rightCount + 1, expression + s[index], removedCount)
        
        
        helper(0, 0, 0, '', 0)
        return self.result

Limited Backtracking:

This algorithm is faster because it only remove the misplaced parentheses.

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        misplacedLeft = misplacedRight = 0
        
        # find all misplaced parentheses 
        for i in range(len(s)):
            if s[i] == '(':
                misplacedLeft += 1
            elif s[i] == ')':
                if misplacedLeft > 0:
                    misplacedLeft -= 1
                else:
                    misplacedRight += 1
        
        # note: use hash set to avoid duplicate result
        result = set()
        
        def helper(left, right, leftToRemove, rightToRemove, index, tmp):
            if index == len(s):
                if leftToRemove == 0 and rightToRemove == 0:
                    # tmp is valid because all misplaced parentheses have been removed
                    result.add(tmp)
            else:
                if s[index] == '(':
                    if leftToRemove > 0:
                        # remove one misplaced 'left' parenthesis
                        helper(left, right, leftToRemove - 1, rightToRemove, index + 1, tmp)

                    # keep the 'left' parenthesis
                    # note: increase the 'left' counter
                    helper(left + 1, right, leftToRemove, rightToRemove, index + 1, tmp + '(')
                elif s[index] == ')':
                    if rightToRemove > 0:
                        # remove one misplaced 'right' parenthesis
                        helper(left, right, leftToRemove, rightToRemove - 1, index + 1, tmp)

                    if left > right:
                        # keep the 'right' parenthesis if it can still maintain a valid string
                        # note : increase the 'right' counter
                        helper(left, right + 1, leftToRemove, rightToRemove, index + 1, tmp + ')')
                else:
                    # keep all letters
                    helper(left, right, leftToRemove, rightToRemove, index + 1, tmp + s[index])
        
        helper(0, 0, misplacedLeft, misplacedRight, 0, '')
        return result

[LeetCode] 257. Binary Tree Paths

Problem : https://leetcode.com/problems/binary-tree-paths/

DFS approach

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        
        def dfs(node):
            if node:
                suffix = []
                
                if node.left:
                    suffix += dfs(node.left)
                    
                if node.right:
                    suffix += dfs(node.right)
                
                return [[str(node.val)] + s for s in suffix] if suffix else [[str(node.val)]]
                
        
        return ['->'.join(path) for path in dfs(root)]

Iterative DFS approach

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        # dfs
        stack = [(root, [root.val])]
        result = []
        
        while stack:
            node, path = stack.pop()
            
            if not node.left and not node.right:
                result.append('->'.join(map(str, path)))
            else:
                if node.right:
                    stack.append((node.right, path + [node.right.val]))
            
                if node.left:
                    stack.append((node.left, path + [node.left.val]))
                
        return result

BFS approach

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        queue = deque([[root]]) if root else deque()
        result = []
        
        while queue:
            path = queue.popleft()
            
            if path[-1].left:
                queue.append(path + [path[-1].left])
            if path[-1].right:
                queue.append(path + [path[-1].right])
            
            if not path[-1].left and not path[-1].right:
                result.append(path)
        
        return map(lambda p: '->'.join(p), map(lambda path: map(lambda n: str(n.val), path), result))

Edited on 04/22/2021. Refactor DFS solution by appending suffix collected from lower level.

Edited on 06/06/2021. Add iterative DFS solution.

[LeetCode] 222. Count Complete Tree Nodes

 Problem : https://leetcode.com/problems/count-complete-tree-nodes/

DFS Solution:

Time Complexity = O ( N )

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def countNodes(self, root: TreeNode) -> int:
        if not root:
            return 0
        
        return 1 + self.countNodes(root.left) + self.countNodes(root.right)
        

BFS Solution:

Time Complexity = O ( N )

# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def countNodes(self, root: TreeNode) -> int:
        if not root:
            return 0
        
        queue = deque([root])
        
        level = 0
        result = 0
        
        while queue:
            tmp = deque()
            result += len(queue)
            while queue:
                node = queue.popleft()
                if node.left:
                    tmp.append(node.left)
                if node.right:
                    tmp.append(node.right)
            
            # stop traversal when reach the last level  
            if len(tmp) < 2 ** level:
                return result + len(tmp)
            
            queue = tmp
        return result

[LeetCode] 200. Number of Islands

 Problem : https://leetcode.com/problems/number-of-islands/

Use counter as flag to mark visited position.

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        row = len(grid)
        if not row:
            return 0
        
        column = len(grid[0])
        
        count = 2
        
        def dfs(y, x, mark):
            if y < 0 or y >= row:
                return
            
            if x < 0 or x >= column:
                return
            
            if grid[y][x] == "1":
                grid[y][x] = mark

                dfs(y-1, x, mark)
                dfs(y+1, x, mark)
                dfs(y, x-1, mark)
                dfs(y, x+1, mark)
            
        
        for y in range(row):
            for x in range(column):
                if grid[y][x] == "1":
                    dfs(y, x, str(count))
                    count += 1
        
        
        return count - 2

[LeetCode] 199. Binary Tree Right Side View

 Problem : https://leetcode.com/problems/binary-tree-right-side-view/

Use BFS to traverse the tree

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        if not root : return []
        
        result = []
        
        queue = deque([root])
        while queue:
            N = len(queue)
            for i in range(N):
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                    
                if node.right:
                    queue.append(node.right)
                
                # append the right-most node value
                if i == N-1:
                    result.append(node.val)
                    
        return result

DFS Solution:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        
        if not root: return []
        
        result = []
        
        # dfs
        stack = [(root, 0)]
        
        while stack:
            node, level = stack.pop()
            
            if level == len(result):
                result.append(node.val)
            
            if node.left:
                stack.append((node.left, level+1))
                
            if node.right:
                stack.append((node.right, level+1))
                    
        return result

Edited on 05/31/2021. Add DFS solution.

[LeetCode] 139. Word Break

Problem : https://leetcode.com/problems/word-break/

Iterate the input string from left to right. Find word in dictionary. If found, break the input string into 2 parts, check if the 2nd part is also constructed by the words in dictionary.

Time Complexity = O ( N )

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        if not wordDict: return False
        
        wordSet = set(wordDict)
        maxLen = max([len(w) for w in wordDict])
        
        @lru_cache(maxsize=None)
        def dfs(start):
            if start >= len(s): 
                return True
            
            for i in range(start, min(start+maxLen, len(s))):
                if s[start:i+1] in wordSet and dfs(i+1):
                    return True
                    
            return False
        
        return dfs(0)

BFS solution:

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        if not wordDict: return False
        wordSet = set(wordDict)
        maxLen = max([len(w) for w in wordDict])
        
        queue = deque([0])
        visited = set([0])
        
        while queue:
            start = queue.popleft()
            
            for i in range(start, min(start+maxLen, len(s))):
                if s[start:i+1] in wordSet:
                    if i + 1 == len(s):
                        return True

                    if i + 1 not in visited:
                        visited.add(i+1)
                        queue.append(i+1)
        
        return False

The bottom-up solution:

class Solution {

    public boolean wordBreak(String s, List wordDict) {
        HashSet<String> words = new HashSet();
        int wordLen = 0;
            
        for (int i = 0; i < wordDict.size(); i++) {
            words.add(wordDict.get(i));
            wordLen = Math.max(wordLen, wordDict.get(i).length());
        }
        
        int N = s.length();
        boolean[] dp = new boolean[N];
        
        for (int i = N-1; i >= 0; i--) {
            for (int j = i; i - j + 1 <= wordLen && j >= 0; j--) {
                
                if (words.contains(s.substring(j, i+1)) && (i + 1 == N || dp[i+1]) ) {
                    dp[j] = true;
                }
            }
        }
        
        return dp[0];

    }
}

Edited on 11/26/2021. Add the bottom-up solution.

[LeetCode] 134. Gas Station

Problem : https://leetcode.com/problems/gas-station/

DFS Solution ( Time Limit Exceeded ) 

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        
        def dfs(start, current, remain):
            if remain < 0:
                return False
            
            if start == current:
                return True
            
            return dfs(start, (current + 1) % len(gas), remain + gas[current] - cost[current])
        
        for i in range(len(gas)):
            if dfs(i, (i + 1) % len(gas), gas[i] - cost[i]):
                return i
        
        return -1

The DFS based solution will time out. However it reveals :

1. To finish a circle, the total gained gas must larger than total used gas

2. At each position, remained gas = last remained gas + gained gas - used gas. 

To reach to the next position, remained gas must larger than 0

If remained gas < 0, it means from the start position to current position, none of them can be used as start point. Because the initial remained gas of start position = 0

Greedy Solution

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        # to finish a circle, gained gas must larger or equal to used gas
        total = 0
        
        # at each pos, remained gas = last remained gas + gained gas - used gas
        # if remained gas < 0, it means from start pos to current pos,
        # none of them can be used as start point.
        # because the initial remained gas of the start position = 0
        remain = 0
        
        start = 0
        
        for i in range(len(gas)):
            
            total += gas[i] - cost[i]
            remain += gas[i] - cost[i]
            
            if remain < 0:
                start = i + 1
                remain = 0
        
        
        return start if total >= 0 else -1