🌐 中文版：繁體中文

Intro

This is my first record of doing a LeetCode Weekly Contest. I jumped on today on a whim, so by the time I was ready to compete there wasn’t much time left. But I’m still a rookie, so I just focused on the first problem to test the waters, and stopped after finishing it.

Problem statement

  • Difficulty: Easy
  • Statement: given an integer array nums, you first pick a starting point curr where nums[curr] = 0. From the starting point you can choose to move left or right, then repeat the following steps:
  1. If curr goes out of the range [0, n-1], the process stops
  2. Move left or right by decrementing/incrementing curr: increasing curr moves right, decreasing curr moves left
  3. After moving, once nums[curr] > 0:
    • decrement nums[curr] by one
    • reverse the current direction of movement
    • take one step in the new direction

A run is considered valid if, once the movement ends, all element values are zero. Return the total number of valid selections.

Solution

Initial idea

First we need to iterate over the given array nums and find the starting points (there may be several). Then, starting from a start point, we walk left or right to judge whether it’s valid. During the traversal, as soon as we hit a value greater than 0 we start walking in the opposite direction, until we reach the far end or another value greater than zero.

My solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
    bool isValid(vector<int>nums, int start, bool direct){
        int n = nums.size();
        int curr = start;
        while(curr >=0 && curr < n) {
            if(nums[curr] ==0){
                if(direct) curr++;
                else curr--;
            }
            else{
                nums[curr]--;
                direct = !direct;
                if(direct) curr++;
                else curr--;
            }
        }
        for(auto it=nums.begin(); it!=nums.end(); ++it){
            if(*it !=0){
                return false;
            }
        }
        return true;
    }

    int countValidSelections(vector<int>& nums){
    
        //select starting position
        int n = nums.size();
        int found = 0;
        for(int i = 0; i< n;i++){
            if(nums[i]==0){
                if(isValid(nums,i,true)){
                    found++;
                }
                if(isValid(nums,i,false)){
                    found++;
                }
            }
        }
        return found;
    }
};

Here I split it into two functions. The main function countValidSelections uses a loop to find the starting points first, and once it finds one it calls isValid twice with different directions. In isValid, we walk back and forth over the elements within the range curr >= 0 && curr < n. Once we hit an element with value zero, we keep walking in the current direction, and if we hit a value greater than 0 we decrement nums[curr] by one and take one step in the reverse direction. After traversing all elements, we check whether every element is now zero; if so it’s valid, otherwise invalid. Back in the main function, if the path is valid we increment the found variable. After trying the different starting points, we can return found.

Execution result

The runtime cost was very high.

Complexity

Time complexity

  • $O(n^2)$

countValidSelections: runs at most $n$ times, and for each starting position isValid is called twice. isValid: in the worst case the while loop traverses the whole array, so $O(n)$, and before returning there’s another loop checking whether every element is 0, which also needs $O(n)$. So the overall time complexity is $2 \times (O(n) + O(n)) = O(4n) = O(n)$ per start, times up to $n$ starts.

Space complexity

  • $O(n)$
    Each call to isValid creates a copy of the array nums, so $O(n)$. In each iteration of countValidSelections, isValid is called twice, but these copies are local and short-lived, so they don’t accumulate. So the overall space complexity is $O(n)$.