LeetCode

Daily LeetCode #5

https://leetcode.com/problems/separate-black-and-white-balls/?envType=daily-question&envId=2024-10-15

To put all zeros onto left and all ones onto right, we need to swap 0 and 1 under the condition that 1 is to the left of 0.

My idea is to use 2 pointers, one starts from left end to locate 1 and the other starts from right end to locate 0.

create two pointers: zeroP and oneP
zeroP starts from right end to locate 0, and oneP starts from left to locate 1
when zeroP finds 0 and oneP finds 1 and zeroP is left to oneP, we need to swap them and add the steps to result
We do not need to actually do the swap, since the digits already visited by pointers will not be visited again
if zeroP and oneP intersects, it means that all the balls are sorted correctly

class Solution {
    public long minimumSteps(String s) {
        int n = s.length();
        int zeroP = n - 1;
        int oneP= 0;
        long res = 0;
        while(oneP < zeroP ) {
            while(s.charAt(zeroP) != '0' && zeroP > 0) {
                zeroP--;
            }

            while(s.charAt(oneP) != '1' && oneP < n-1) {
                oneP++;
            }

            if (oneP < zeroP)  res += (zeroP - oneP);
           
            oneP++;
            zeroP--;
        }
        return res;
    }
}

Notes:

need to use long for res since we need to return a long
use two while loops inside the main while loop to let both pointers locate 0 or 1
check condition oneP < zeroP again in the loop to ensure that two pointers are not yet intersected

Time Complexity: O(n) [only iterates the string once]

Space Complexity: O(1)

Another idea is to swap the groups of 1s together.

class Solution {
    public long minimumSteps(String s) {
        long res = 0;   
        int blackCount = 0;

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '1') {
                blackCount++;
            } else {
                res += blackCount;
            }
        }

        return res;
    }
}

Start from the left end, if we see a 1, swap it with the nearest 0. If we meet other 1s , we need to swap not only the new encountered 1 but also the previous 1. We use blackCount for this use.

Time Complexity and Space Complexity are the same.

Some notes on problems from SQL 50.

https://leetcode.com/problems/students-and-examinations/description/?envType=study-plan-v2&envId=top-sql-50

SELECT Stu.student_id, Stu.student_name, S.subject_name, COUNT(E.subject_name) AS attended_exams
FROM Students AS Stu JOIN Subjects AS S LEFT OUTER JOIN Examinations AS E 
                ON Stu.student_id = E.student_id AND S.subject_name = E.subject_name
GROUP BY Stu.student_id, Stu.student_name, S.subject_name
ORDER BY Stu.student_id, Stu.student_name

Notes:

the first JOIN between Students and Subjects generates student identity and subject combinations
the second LEFT OUTER JOIN aims to filter valid records
GROUP BY needs to be used on three attributes, since the combination of them serves as the primary key
COUNT() cannot be used on attributes from table other than Examinations, because if some student does not attend some subjects, the blanks will be NULL due to LEFT OUTER JOIN

https://leetcode.com/problems/managers-with-at-least-5-direct-reports/?envType=study-plan-v2&envId=top-sql-50

SELECT E.name
FROM Employee AS E
WHERE E.id IN (SELECT managerId
             FROM Employee
             GROUP BY managerId
             HAVING count(*) >= 5)

Use subquery to find the qualified id.

SELECT E2.name
FROM Employee AS E1 JOIN Employee AS E2
WHERE E1.managerId = E2.id
GROUP BY E1.managerId
HAVING count(E2.name) >= 5

But for the same problem, not sure why this query is not working...

Sol: Need to change E2.name in the last line to E2.Vdepartment, because count() does not consider NULL.

https://leetcode.com/problems/confirmation-rate/description/

SELECT S.user_id, IFNULL(round(sum(IF(C.action = "confirmed", 1, 0))/count(C.action), 2), 0) AS confirmation_rate
FROM Signups AS S LEFT OUTER JOIN Confirmations AS C ON S.user_id = C.user_id
GROUP BY S.user_id

Use LEFT OUTER JOIN to make user_id that does not appear in Conformation table to NULL
Function IF(a, b, c):
if condition a is satisfied, return b; else return c
Function IFNULL(a, b):
if a is not NUll, return a; else return b