[LeetCode] 594. Longest Harmonious Subsequence

Problem : https://leetcode.com/problems/longest-harmonious-subsequence/description/

Since we only need the length of the subsequence, we don't need to preserve the original order of the numbers. We can sort the origin array in non-decreasing order and use sliding window to find the longest subsequence.

The left pointer points to the minmum value and the right pointer points to the maximum value.

Move left pointer to right, when the difference is larger than 1.

Move right pointer to right, when the difference is smaller or equal to 1.

Update the longest subsequence length when the difference is equal to 1.

class Solution {
    public int findLHS(int[] nums) {
        Arrays.sort(nums);

        int left = 0; 
        int result = 0;
        for (int right = 0; right < nums.length;) {
            long diff = nums[right] - nums[left];
            if (diff < 1L) {
                right++;
                continue;
            }
            if (diff == 1L) {
                result = Math.max(result, right - left + 1);
                right++;
                continue;
            }
            left += 1;
        }
        
        return result;
    }

[LeetCode] 1007. Minimum Domino Rotations For Equal Row

Problem : https://leetcode.com/problems/minimum-domino-rotations-for-equal-row/description/

To reach the goal of this problem, we can:

Lock the first column and rotate the other columns to match the top value the first column.

Lock the first column and rotate the other columns to match the bottom value the first column.

Rotate and lock the first column, then rotate the other columns to match the top value of the first column.

Rotate and lock the first column, then rotate the other columns to match the bottom value of the first column.

The answer is minimum rotation count of the above 4 usecases.

class Solution {
    public int minDominoRotations(int[] tops, int[] bottoms) {
        int rotationCountForMatchingTop = helper(tops[0], tops, bottoms);
        int rotationCountForMatchingBottom = helper(bottoms[0], tops, bottoms);
        
        if (rotationCountForMatchingTop == -1 && rotationCountForMatchingBottom == -1)
          return -1;

        if (rotationCountForMatchingTop == -1)
          return rotationCountForMatchingBottom;

        if (rotationCountForMatchingBottom == -1)
          return rotationCountForMatchingTop;

        return Math.min(rotationCountForMatchingTop, rotationCountForMatchingBottom);
    }

    int helper(int target, int[] A, int[] B) {
      int rotateToTop = 0, rotateToBottom = 0;
      for (int i = 0; i < A.length; i++) {
        if (target != A[i] && target != B[i]) {
          // There is no way to rotate the current domino to match the target value.
          return -1;
        }

        if (target != A[i]) {
          rotateToTop += 1;
        }

        if (target != B[i]) {
          rotateToBottom += 1;
        }
      }

      return Math.min(rotateToTop, rotateToBottom);
    }
}

[LeetCode] 2140. Solving Questions With Brainpower

Problem: https://leetcode.com/problems/solving-questions-with-brainpower/description/

Similar to the House Robber problem. For each question, we need to consider these 2 cases:

The point we can get if we solve this problem and solve or skip the next eligible problem.

The point we can get if we skip this problem and solve or skip the next eligible problem.

Time Complexity : O ( N )

Space Complexity : O ( N )

class Solution {
    public long mostPoints(int[][] questions) {
        int N = questions.length;

        // maximum point when pick the 'i' question
        long[] pick = new long[N];
        // maximum point when skip the 'i' question
        long[] skip = new long[N];

        for (int i = N-1; i >= 0; i--) {
          // solve the 'i' question
          pick[i] = questions[i][0];

          int j = i + questions[i][1] + 1;
          if (j < N) {
            // add on the point of picking / skip next eligible question 
            pick[i] += Math.max(pick[j], skip[j]);
          }

          // skip the 'i' question
          if (i + 1 < N) {
            // add on the point of picking / skip the next question 
            skip[i] = Math.max(pick[i+1], skip[i+1]);
          }
        }

        return Math.max(pick[0], skip[0]);
    }
}