This section contains Leetcode problems that are a bit more general than problems we have encountered so far. In other words, there are many methods to solve problems efficiently.

Leetcode Problem #744 - FInd the Smallest Letter Greater than Target

Here is the problem

So I didn’t get this problem in a single try. I forgot about the fact that the letters wrap around for this problem. So, if target is “z” and our letters is [“a”,”b”]. Then the answer is “a”. We will use binary search.

• As usual, we will use mid = low + (high - low ) // 2 to prevent overflowing happening. Also, low and high will be 0 and len(letters) - 1 respectively.
• Now, since we are looking for the smallest character in the array that’s larger than target, we have to use “if target >= letters[low]” (pay attention to the greater than or equal to inequality). Try the case with strict inequality for a test case of [“c”, “f”, “j”] with target letter “c”. You will get time limit exceeded.
• Next, when we exit the While loop of our binary search, we have to do a bit more postprocessing work for this problem, because of that wrapping. Let’s consider a test case, where we have [“c”, “f”, “j”] for an array, letters, and target letter of “j”. The expected answer is “c”, since we are essentially dealing with an array like this [“c”, “f”, “j”, “c”, “f”, “j”, … ]. (I know.. this problem is not exactly my favorite problem). So if we simply return letters[low], then we get “j” instead of “c”. How do we deal with this? If low == len(letters) - 1 (in other words, when low is pointing at the last index), that’s the case where we have to be a bit careful. So if low == len(letters) - 1 is True, then we have to check whether (1) target is greater than or equal to the last element of this letters. If True, then we return the FIRST element of the array letters (letters[0]). (2) If target is less than the last element of the array, we return the last element ( try letters = [“c”, “f”, “j”] with target “g”. The answer we want is “j”).

Below is the code.

class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        low, high = 0, len(letters) - 1
        
        while low < high: 
            mid = low + (high - low) // 2
            if letters[mid] <= target:
                low = mid + 1
            elif letters[mid] > target:
                high = mid

                
        if low == len(letters) - 1:
            if target >= letters[low]:
                return letters[0]
            else:
                return letters[-1]
        else:
            return letters[low]
        

Leetcode Problem #1423 - Maximum Points You Can Obtain from Cards

Here is the problem

Well, I initially thought about constructing a binary tree. For instance, let’s use cardPoints = [2,10,8,7,1,4,3] with K = 3. Then there are $2^3 = 8$ ways of representing a subarray adhering to the constraints of the problem. However, notice that we find lots of duplicate. Because we are only interested in finding the maximum number the subarray can have, we can discard duplicate numbers. When I say duplicate numbers, I mean the subarrays that have same numbers in it - [2,3,10] and [2,10,3] are the same.

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        result = 0 
        
        #from the 0th to k-1th position
        for i in range(0,k):
            result += cardPoints[i]
        
        answer = result 
        for i in range(k-1, -1, -1):
            s = len(cardPoints) - k 
            result = result - cardPoints[i] + cardPoints[i + s]
            answer = max(answer, result )
        return answer         

=====