Solution of Biweekly Contest 18

, , , , , ,

[Easy] 1331. Rank Transform of an Array

Given an array of integers arr, replace each element with its rank.

The rank represents how large the element is. The rank has the following rules:

  • Rank is an integer starting from 1.
  • The larger the element, the larger the rank. If two elements are equal, their rank must be the same.
  • Rank should be as small as possible.

Example

1
2
3
4
5
6
7
8
9
10
Input: arr = [40,10,20,30]
Output: [4,1,2,3]
Explanation: 40 is the largest element. 10 is the smallest. 20 is the second smallest. 30 is the third smallest.

Input: arr = [100,100,100]
Output: [1,1,1]
Explanation: Same elements share the same rank.

Input: arr = [37,12,28,9,100,56,80,5,12]
Output: [5,3,4,2,8,6,7,1,3]

Solution

Actually, it should be sorting problem. We have to keep track of each distinct number, so we have to sort and then use the hashmap to keep track the position, and then we iterate originial array to place our result.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// time: O(nlogn) space:O(n)
  public int[] arrayRankTransform(int[] arr) {
      if (arr == null || arr.length == 0) return new int[]{};
      int[] sort = arr.clone();
      Arrays.sort(sort);
      HashMap<Integer, Integer> map = new HashMap<>();
      int rank = 1;
      for (int i = 0; i < sort.length; i++) {
          if (! map.containsKey(sort[i])) {
              map.put(sort[i], rank++);
          }
      }
      int[] res = new int[arr.length];
      for (int i = 0; i < arr.length; i++) {
          res[i] = map.get(arr[i]);
      }
      return res;
  }

[Medium] 1328. Break a Palindrome

Given a palindromic string palindrome, replace exactly one character by any lowercase English letter so that the string becomes the lexicographically smallest possible string that isn’t a palindrome.

After doing so, return the final string. If there is no way to do so, return the empty string.

Example

1
2
3
4
5
Input: palindrome = "abccba"
Output: "aaccba"

Input: palindrome = "a"
Output: ""

Solution

We have to find first non-‘a’ char to convert to ‘a’, during the process, we have to verify if it is palindrome. If it didn’t work after go through all elements in array, then we have to see if the length is greater than 1, we have to change the last char to ‘b’ and then return it. (Edge cases need to considered!)

Code

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
// time:O(n) space: O(n)
  public String breakPalindrome(String palindrome) {
      // edge case:
      // "aa" -> "ab";
      // "aaabaaa" -> "aaabaab"
      // change the first char which is not a.
      if (palindrome == null || palindrome.length() == 0) return "";
      char[] chs = palindrome.toCharArray();
      boolean atEnd = false;
      for (int i = 0; i < chs.length; i++) {
          if (chs[i] != 'a') {
              char ch = chs[i];
              chs[i] = 'a';
              if (!isValid(new String(chs))) return new String(chs);
              chs[i] = ch;
          }
          // to see if it didn't work or all 'a'
          if (i == chs.length - 1) atEnd = true;
      }
      if (atEnd && chs.length > 1) {
          chs[chs.length - 1] = 'b';
          return new String(chs);
      }
      return "";
  }

  public boolean isValid(String s) {
      int left = 0;
      int right = s.length() - 1;
      while (left < right) {
          if (s.charAt(left) != s.charAt(right)) return false;
          left++;
          right--;
      }
      return true;
  }

[Medium] 1329. Sort the Matrix Diagonally

Given a m * n matrix mat of integers, sort it diagonally in ascending order from the top-left to the bottom-right then return the sorted array.

1
2
Input: mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]					
Output: [[1,1,1,1],[1,2,2,2],[1,2,3,3]]

Solution

Sort them Diagonally.

Code

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
// time: O(m + n) max log max(# of diag)
// space: O(m * n) clone
    public int[][] diagonalSort(int[][] mat) {
        if (mat == null || mat.length == 0 || mat[0] == null || mat[0].length == 0) return new int[][]{};
        int m = mat.length;
        int n = mat[0].length;
        for (int j = n - 1; j >= 0; j--) {
            int col = j;
            int row = 0;
            List<Integer> list = new LinkedList<>();
            while (row < m && col < n) {
                list.add(mat[row][col]);
                row++;
                col++;
            }
            Collections.sort(list);
            col = j;
            row = 0;
            int k = 0;
            while (row < m && col < n) {
                mat[row][col] = list.get(k++);
                row++;
                col++;
            }
        }

        for (int i = 1; i < m; i++) {
            int col = 0;
            int row = i;
            List<Integer> list = new LinkedList<>();
            while (row < m && col < n) {
                list.add(mat[row][col]);
                row++;
                col++;
            }
            Collections.sort(list);
            col = 0;
            row = i;
            int k = 0;
            while (row < m && col < n) {
                mat[row][col] = list.get(k++);
                row++;
                col++;
            }
        }
        return mat;
    }

// Priority Queue. analysis would be same as before.
public int[][] diagonalSort2(int[][] mat) {
        if (mat == null || mat.length == 0 || 
            mat[0] == null || mat[0].length == 0) 
            return new int[][]{};
        int m = mat.length;
        int n = mat[0].length;
        // use i - j to identify each diag.
        HashMap<Integer, PriorityQueue<Integer>> diag = new HashMap<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                diag.putIfAbsent(i - j, new PriorityQueue<>());
                diag.get(i - j).add(mat[i][j]);
            }
        }
        
        // poll each diag
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                mat[i][j] = diag.get(i - j).poll();
            }
        }
        return mat;
    }

[Hard] 1330. Reverse Subarray To Maximize Array Value [TLE during contest]

You are given an integer array nums. The value of this array is defined as the sum of |nums[i]-nums[i+1]| for all 0 <= i < nums.length-1.

You are allowed to select any subarray of the given array and reverse it. You can perform this operation only once.

Find maximum possible value of the final array.

Example

1
2
3
4
5
6
Input: nums = [2,3,1,5,4]
Output: 10
Explanation: By reversing the subarray [3,1,5] the array becomes [2,5,1,3,4] whose value is 10.

Input: nums = [2,4,9,24,2,1,10]
Output: 68

It’s hard to me.

Rank: 528 / 3007. Solve 3/4 in 1 hour 30 min.