Solution of Weekly Contest 169

[Easy] 1304. Find N Unique Integers Sum up to Zero

Given an integer n, return any array containing n unique integers such that they add up to 0.

Example

Input: n = 5
Output: [-7,-1,1,3,4]
Explanation: These arrays also are accepted [-5,-1,1,2,3] , [-3,-1,2,-2,4].

Solution

We have to consider the even and odd situations. if it is odd, set the middle element as 0 and spread left (–) and right (++), if it is even, set the pairs, such as (-1,1), (-2, 2)...

Code

// time:O(n) space:O(n)
public int[] sumZero(int n) {
        if (n < 0) return new int[]{};
        int[] res = new int[n];
        int start = 0, end = n / 2 - 1;
        if (n % 2 == 0) {
            start = n / 2;
        } else {
            start = n / 2 + 1;
            res[n / 2] = 0;
        }
        int k = -1;
        for (int i = end; i >= 0; i--) {
            res[i] = k;
            k--;
        }
         k = 1;
        for (int i = start; i < n; i++) {
            res[i] = k;
            k++;
        }
        return res;
    }

[Medium] 1305. All Elements in Two Binary Search Trees

Given two binary search trees root1 and root2.

Return a list containing all the integers from both trees sorted in ascending order.

Example

Input: root1 = [2,1,4], root2 = [1,0,3]
Output: [0,1,1,2,3,4]

Input: root1 = [0,-10,10], root2 = [5,1,7,0,2]
Output: [-10,0,0,1,2,5,7,10]

Solution

Use iterative approach to solve and needs to keep tracking two stacks.

Code

//time:O(n) space:
public void pushLeft(Stack<TreeNode> stack, TreeNode root) {
        if (root == null) return;
        stack.push(root);
        pushLeft(stack, root.left);
    }
    
    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> s1 = new Stack<>();
        Stack<TreeNode> s2 = new Stack<>();
        pushLeft(s1, root1);
        pushLeft(s2, root2);
        while (!s1.isEmpty() || !s2.isEmpty()) {
            Stack<TreeNode> s = null;
            if (!s1.isEmpty() && !s2.isEmpty()) {
                s = s1.peek().val > s2.peek().val ? s2 : s1;
            } else if (s1.isEmpty()) {
                s = s2;
            } else if (s2.isEmpty()) {
                s = s1;
            }
            TreeNode current = s.pop();
            res.add(current.val);
            pushLeft(s, current.right);
        }
        return res;
    }

[Medium] 1306. Jump Game III

Given an array of non-negative integers arr, you are initially positioned at start index of the array. When you are at index i, you can jump to i + arr[i] or i - arr[i], check if you can reach to any index with value 0.

Notice that you can not jump outside of the array at any time.

Example

Input: arr = [4,2,3,0,3,1,2], start = 5
Output: true
Explanation: 
All possible ways to reach at index 3 with value 0 are: 
index 5 -> index 4 -> index 1 -> index 3 
index 5 -> index 6 -> index 4 -> index 1 -> index 3

Input: arr = [4,2,3,0,3,1,2], start = 0
Output: true 
Explanation: 
One possible way to reach at index 3 with value 0 is: 
index 0 -> index 4 -> index 1 -> index 3

Solution

We use backtracking strategy to solve this problem and try to iterate all the possibilities. During the process, we also have to keep tracking what element has already visited and prevent TLE.

Code

DFS

// time:O(n) space:O(n)
public boolean canReach(int[] arr, int start) {
        int n = arr.length;
        if (arr == null || arr.length == 0) return false;
        boolean[] visited = new boolean[n];
        return dfs(arr, start, visited);
    }


    public boolean dfs(int[] arr, int start, boolean[] visited) {
        if (start >= arr.length || start < 0) return false;
        if (arr[start] == 0) return true;
        if (visited[start]) return false;
        visited[start] = true;
        return dfs(arr, start + arr[start], visited) || dfs(arr, start - arr[start], visited);
    }

BFS

// time:O(n) space:O(n)
public boolean canReach(int[] arr, int start) {
        int n = arr.length;
        if (arr == null || arr.length == 0) return false;
        boolean[] visited = new boolean[n];
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        visited[start] = true;
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            if (arr[curr] == 0) return true; 
            if (curr + arr[curr] < n && !visited[curr + arr[curr]]) {
                queue.offer(curr + arr[curr]);
                visited[curr + arr[curr]] = true;
            }
            if (curr - arr[curr] >= 0 && !visited[curr - arr[curr]]) {
                queue.offer(curr - arr[curr]);
                visited[curr - arr[curr]] = true;
            }
        }
        return false;
    }

Rank: 2778 / 5933. Solved 3/4 in 1:24:46