Solution of Biweekly Contest 16

[Easy] 1299. Replace Elements with Greatest Element on Right Side

Given an array arr, replace every element in that array with the greatest element among the elements to its right, and replace the last element with -1.

After doing so, return the array.

Example

Input: arr = [17,18,5,4,6,1]
Output: [18,6,6,6,1,-1]

Solution

• Brute force: look through each element and then calculate the maximum value of rest number (use two for loop)
• Elegant solution: look each element backward and calculate the maximum.

Code

// time:O(n^2) space:O(n)
  public int[] replaceElements(int[] arr) {
      if (arr == null || arr.length == 0) return new int[]{};
      int[] res = new int[arr.length];

      for (int i = 0; i < arr.length; i++) {
          int max = -1;
          for (int j = i + 1; j < arr.length; j++) {
              max = Math.max(max, arr[j]);
          }
          res[i] = max;
      }
      return res;
  }

// time:O(n) space:O(1)
  public int[] replaceElements2(int[] arr) {
      // look backward
      if (arr == null || arr.length == 0) return new int[]{};
      int max = -1;
      for (int i = arr.length - 1; i >= 0; i--) {
          int temp = arr[i];
          arr[i] = max;
          max = Math.max(max, temp);
      }
      return arr;
  }

1300. Sum of Mutated Array Closest to Target

Given an integer array arr and a target value target, return the integer value such that when we change all the integers larger than value in the given array to be equal to value, the sum of the array gets as close as possible (in absolute difference) to target.

In case of a tie, return the minimum such integer.

Notice that the answer is not neccesarilly a number from arr.

Example

Input: arr = [4,9,3], target = 10
Output: 3
Explanation: When using 3 arr converts to [3, 3, 3] which sums 9 and that's the optimal answer.

Input: arr = [2,3,5], target = 10
Output: 5

Input: arr = [60864,25176,27249,21296,20204], target = 56803
Output: 11361

Solution

Using Binary Search. Iterate from 1 to target and calculate the sum and also keep the minimum difference.

At the end, we have to check the left and right.

Code

	// time:O(NlogM), N = # of arr, M = # of target.
// space:O(1)
public int findBestValue(int[] arr, int target) {
       if (arr == null || arr.length == 0) return 0;
       int left = 0;
       int right = target;
       int choose = 0;
       int diff = Integer.MAX_VALUE;
       while (left + 1 < right) {
           int mid = left + (right - left) / 2;
           int sum = calSum(arr, mid);
           if (Math.abs(sum - target) < diff) {
               diff = Math.abs(sum - target);
               choose = mid;
           }
           if (sum >= target) {
               right = mid;
           } else {
               left = mid;
           }
       }
       if (Math.abs(calSum(arr, left) - target) < diff) return left;
       if (Math.abs(calSum(arr, right) - target) < diff) return right;
       return choose;
   }

   public int calSum(int[] arr, int choose) {
       int sum = 0;
       for (int num : arr) {
           if (num > choose) sum += choose;
           else sum += num;
       }
       return sum;
   }

1302. Deepest Leaves Sum

Given a binary tree, return the sum of values of its deepest leaves.

Example

Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
Output: 15

Solution

We can use either DFS or BFS, for the DFS, first we need to calculate the maximum depth and use that value to helpe return the deepest node val, otherwise, it returns 0. And then we have to sum up left side and right side. For the BFS, we just need to keep tracking sum of each level and at the end, return the last level’s vlaue.

Code

	// DFS
	// time:O(n) space:O(n)
   public int deepestLeavesSum(TreeNode root) {
       if (root == null) return 0;
       int depth = maxDis(root);
       return helperWithReturn(root, depth);
   }

   public int helperWithReturn(TreeNode root, int level) {
       if (root == null) return 0;
       if (level == 1) return root.val;// at the deepest node.
       int left = helperWithReturn(root.left,level - 1);
       int right = helperWithReturn(root.right, level - 1);
       return left + right;
   } 

   public int maxDis(TreeNode root) {
       if (root == null) return 0;
       int left = maxDis(root.left);
       int right = maxDis(root.right);
       return Math.max(left, right) + 1;
   }

// BFS
 // time:O(n) space:O(n)
public int deepestLeavesSum2(TreeNode root) {
       if (root == null) return 0;
       Queue<TreeNode> queue = new LinkedList<>();
       int sum = 0;
       queue.offer(root);
       while (!queue.isEmpty()) {
           int size = queue.size();
           sum = 0; // calculate each level.
           for (int i = 0; i < size; i++) {
               TreeNode node = queue.poll();
               sum += node.val;
               if (node.left != null) {
                   queue.offer(node.left);
               }
               if (node.right != null) {
                   queue.offer(node.right);
               }
           }
       }
       return sum;
   }

1301. Number of Paths with Max Score

To be continued.

Rank: 636 / 2788. Solve 3/4 in 1 hour 30 min.