DEV Community: truongductri01

678. Valid Parenthesis String

truongductri01 — Sun, 22 Oct 2023 03:12:52 +0000

First Approach

Can utilize a similar method like validating parenthesis.

Loop through each char c in the string s and check:

if c == *, increase countStar
if c == (, increase countLeft
if c == ), decrease countLeft if countLeft > 0. otherwise, if countStar > 0, decrease it, else return false.

At the end, if countStar >= countLeft, return true, else, return false.

This may sound like a good approach but this will fail since there is another restriction that we have not taken into consideration:
Left parenthesis '(' must go before the corresponding right parenthesis ')'.

That means if there is a star and a left parenthesis, the star must come after.

Correct Approach

We will utilize Stack and Queue to keep track of the index of the left parenthesis and the stars.

After removing all the right parenthesis like mentioned above, we will check the positions of the stars and left parenthesis to make sure it meet the requirements

Here is a simple explanation:

used stack for left paren and queue for star?
will store the int value (the index of the parent and star only)
if there is some right paren without left paren remove star from the top of the queue (smallest positions)

when there are only left paren left.

pop from the end => get the largest, if it does not satisfy => false
convert queue into stack for popped out
keep doing until empty

class Solution {
    public boolean checkValidString(String s) {
        Queue<Integer> starQ = new LinkedList<>();
        Stack<Integer> leftS = new Stack<>();


        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '*') {
                starQ.add(i);
            } else if (c == '(') {
                leftS.add(i);
            } else {
                // ) only 
                if (!leftS.isEmpty()) {
                    leftS.pop();
                } else {
                    if (!starQ.isEmpty()) {
                        starQ.remove();
                    } else {
                        return false;
                    }
                }
            }
        }

        if (leftS.isEmpty()) {
            return true;
        } else if (starQ.isEmpty()) {
            // this means still has left but no star 
            return false;
        } else {
            // convert 
            Stack<Integer> starS = new Stack<>();
            while (!starQ.isEmpty()) {
                starS.add(starQ.remove());
            }

            while (!starS.isEmpty() && !leftS.isEmpty()) {
                int left = leftS.pop();
                int star = starS.pop();

                if (star < left) {
                    return false;
                }
            }

            if (leftS.isEmpty()) {
                return true;
            }
            return false;
        }
    }
}

1584. Min Cost to Connect All Points

truongductri01 — Sun, 15 Oct 2023 17:34:31 +0000

Problem: 1584. Min Cost to Connect All Points

Explain

Looking at the problem, we can identify this as a Graph problem. And in order to find the minimum cost to connect all points, we need to establish the minimum spanning tree.
We can either use Kruskal's or Prim's algorithm. I will go with Prim's algorithm for this solution.

For Prim's algo, we will create a minimum spanning tree by expanding from 1 node, adding new nodes which has the smallest edge and repeat until we reach the final result.
We will need a min heap to keep track of the edge with the smallest distance value.

In the code, you will see a while loop, the condition to break that is either the heap is empty or we already have all nodes marked as visited.

Solution

class Solution {
    class Edge {
        int[] p1;
        int[] p2;
        int distance;
        int index1;
        int index2;

        public Edge (int[] p1, int index1, int[] p2, int index2) {
            this.p1 = p1;
            this.p2 = p2;
            this.distance = Math.abs(p1[0] - p2[0]) + Math.abs(p1[1] - p2[1]);
            this.index1 = index1;
            this.index2 = index2;
        }
    }

    public int minCostConnectPoints(int[][] points) {
        if (points.length == 1) {
            return 0;
        }
        // Start with any points, add all possible path into a Queue
        // take out the smallest distance in the queue such that one node is in the connected and on is not
        // only add the edges comes after the index

        PriorityQueue<Edge> pq = new PriorityQueue<>((a, b) -> a.distance - b.distance);
        int[] parents = new int[points.length];
        Set<Integer> visited = new HashSet<>();
        Set<Integer> notVisited = new HashSet<>();

        for (int i = 0; i < parents.length; i++) {
            parents[i] = i;
            notVisited.add(i);
        }
        visited.add(0);
        notVisited.remove(0);


        int result = 0;

        for (int i = 1; i < points.length; i++) {
            // create the Edge
            Edge edge = new Edge(points[0], 0, points[i], i);
            pq.add(edge);
        }

        while (!pq.isEmpty() && visited.size() < points.length) {
            // take the first pair
            Edge edge = pq.remove();

            // make sure they do not create a cycle.

            if (visited.contains(edge.index1) && visited.contains(edge.index2)) {
                continue;
            } else {
                result += edge.distance;
                for (int i: notVisited) {
                    Edge newEdge = new Edge(points[edge.index2], edge.index2, points[i], i);
                    pq.add(newEdge);
                }
                visited.add(edge.index2);
                notVisited.remove(edge.index2);
            }
        }

        return result;
    }
}

647. Palindromic Substrings

truongductri01 — Wed, 11 Oct 2023 17:59:30 +0000

Problem: 647. Palindromic Substrings

Approaches

Simplest approach will be checking all possible combinations of the substrings and check which one is palindromic

O(n ^ 2) with each string to be around n / 2
=> O(n ^ 3) => more than 10 ^ 9
and working with string is not so good
Can we apply DP here to keep track of the palindrom that is already checked
dp[][]

dp[i][j] will be either 0, 1, or 2
with 0 is unknown
with 1 is false
and 2 is true

dp[i][j] = 1 means that is not palindromic
dp[i][j] = 2 means palindromic checked

if the string has length 1 => true for sure

else:
check dp first
check the first and last string then check recurse(left + 1, right - 1);

This will require to start with each substring starting with a specific index and check the length of it

At most, a substring can have a length of n
check from length 1 to length n
with that,

with length l, check from index 0 till index i as long as i + l < n; i++

Solution

class Solution {
    int[][] dp;
    String string;

    public int recurse(int start, int end) {
        if (dp[start][end] != 0) {
            return dp[start][end];
        } else {
            int isPalindromic = 0;

            if (start == end) {
                isPalindromic = 2;
            } else if (string.charAt(start) != string.charAt(end)) {
                isPalindromic = 1;
            } else { // char at start and end are equal
                if (start + 1 == end) { 
                    isPalindromic = 2;
                } else {
                    isPalindromic = recurse(start + 1, end - 1);
                }
            } 

            dp[start][end] = isPalindromic;
            return dp[start][end];
        }
    }

    public int countSubstrings(String s) {
        string = s;
        dp = new int[string.length()][string.length()];

        for (int r = 0; r < dp.length; r ++) {
            for (int c = 0; c < dp.length; c++) {
                dp[r][c] = 0; // fill with unknown
            }
        }

        for (int length = 1; length <= s.length(); length ++) {
            for (int idx = 0; idx + length - 1 < s.length(); idx ++) {
                // StringBuilder sb = new StringBuilder();
                // for (int i = idx; i < idx + length; i++) {
                //     sb.append(s.charAt(i));
                // }
                // System.out.println(sb.toString());

                recurse(idx, idx + length - 1);
            }
        }    

        int result = 0;
        for (int r = 0; r < dp.length; r ++) {
            for (int c = 0; c < dp.length; c++) {
                if (dp[r][c] == 2) result ++;
            }
        }
        return result;
    }
}

74. Search a 2D Matrix

truongductri01 — Sun, 08 Oct 2023 03:22:23 +0000

Problem: 74. Search a 2D Matrix

Approach

/**
Definitely binary search

2 steps:
- search for which row the target should fall into 
- then search within that row for the target 


How to search for which row 
hasRow = false;
int rowIdx = -1;
leftRow and rightRow

while (leftRow <= rightRow) {
    int midRow;

    if (target within midRow) {
        hasRow = true;
        rowIdx = midRow;
    }

    if (target < midRow[0]) {
        right = midRow - 1;
    } else if (target > midRow[size - 1]) {
        left = midRow + 1;
    }
}

if not found row: return false;

else, find within the row

*/


class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        boolean hasRow = false;
        int rowIdx = -1;

        int leftRow = 0;
        int rightRow = matrix.length - 1;
        int columns = matrix[0].length;

        while (leftRow <= rightRow) {
            int midRow = (leftRow + rightRow) / 2;

            if (target >= matrix[midRow][0] && target <= matrix[midRow][columns - 1]) {
                hasRow = true;
                rowIdx = midRow;
                break;
            } else if (target < matrix[midRow][0]) {
                rightRow = midRow - 1;
            } else if (target > matrix[midRow][columns - 1]) {
                leftRow = midRow + 1;
            }
        }

        if (!hasRow) {
            return false;
        }

        int left = 0;
        int right = columns - 1;

        while (left <= right) {
            int mid = (left + right) / 2;

            if (target == matrix[rowIdx][mid]) {
                return true;
            } else if (target < matrix[rowIdx][mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return false;
    }
}

23. Merge k Sorted Lists

truongductri01 — Thu, 05 Oct 2023 04:45:39 +0000

Problem: 23. Merge k Sorted Lists

Solution

If you are able to solve the merge 2 sorted linked list, you will be able to do this

By spliting k lists into groups of a pair of linked lists, we can merge each pair, then repeat the process until there is only one big sorted list left to be returned.
Remember to handle edge case like when there is no linked list in the list at all then we should be good.


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode merge2Lists(ListNode node1, ListNode node2) {
        ListNode dummy = new ListNode(-1);
        ListNode dummyCurrent = dummy;
        ListNode current1 = node1;
        ListNode current2 = node2;

        while (current1 != null && current2 != null) {
            if (current1.val <= current2.val) {
                dummyCurrent.next = current1;
                current1 = current1.next;
            } else {
                dummyCurrent.next = current2;
                current2 = current2.next;
            }
            dummyCurrent = dummyCurrent.next;
        }

        while (current1 != null) {
            dummyCurrent.next = current1;
            current1 = current1.next;
            dummyCurrent = dummyCurrent.next;
        }

        while (current2 != null) {
            dummyCurrent.next = current2;
            current2 = current2.next;
            dummyCurrent = dummyCurrent.next;
        }

        return dummy.next;
    }
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }

        List<ListNode> initialList = new ArrayList<>();
        for (ListNode node: lists) {
            initialList.add(node);
        }

        while (initialList.size() > 1) {
            List<ListNode> newList = new ArrayList<>();
            int idx = 0;
            while (idx < initialList.size()) {
                if (idx == initialList.size() - 1) {
                    newList.add(initialList.get(idx));
                    idx ++;
                } else {
                    newList.add(merge2Lists(initialList.get(idx), initialList.get(idx + 1)));
                    idx += 2;
                }
            }
            initialList = newList;
        }

        return initialList.get(0);
    }
}

207. Course Schedule

truongductri01 — Sun, 01 Oct 2023 03:55:00 +0000

Problem: 207. Course Schedule

Implementation:

/**
What makes the code return false:
- cannot take the class. why?
- there is a cycle. need a for b but then need b for a. like a deadlock => false. 

This looks like a graph. => just need to determine if there is a cycle. 
- we can use BFS for this. Keep traversing until reaching the end. While at the end, make sure to also utilize DP to keep track whether all courses could be taken succesfully

Steps:
1. Establish the mapping representing the courses relationship. If a needs b, c, d then:
{
    a: list(b, c, d, ...)
}

2. Start BFS: on all key:
    DP map: Map<String, Boolean> map 

    for all keys in map: call could_take(key, new HashSet<>())

    could take a?, visited: Set<String>:
        if key in dpMap: return dpMap.get(key)
        else if a not in the map:
            dpMap.put(key, true)
        else if key in visited:
            return false;
        else: 
            can = true?
            visited.add(can)
            for prere in map.get(a):
                can_prere = could take prereq(prere, visited)
                if !can_prere:
                    can = false
                    break
            dpMap.put(key, can);
        return dpMap.get(key);

3. At the end:
    loop through all keys in DP, if there is a course that could not be taken, return false.
*/

class Solution {
    Map<Integer, Boolean> dpMap;
    Map<Integer, Set<Integer>> map;

    public boolean couldTake(int course, Set<Integer> visited) {
        if (dpMap.containsKey(course)) {
            return dpMap.get(course);
        } else if (!map.containsKey(course)) {
            dpMap.put(course, true);
        } else if (visited.contains(course)) {
            dpMap.put(course, false);
        } else {
            boolean possible = true;
            visited.add(course);
            for (int pre: map.get(course)) {
                if (!couldTake(pre, visited)) {
                    possible = false;
                    break;
                }
            }
            dpMap.put(course, possible);
        }
        return dpMap.get(course);
    }

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        this.dpMap = new HashMap<>();
        this.map = new HashMap<>();

        // create the mapping
        for (int[] pre: prerequisites) {
            int first = pre[0];
            int second = pre[1];
            // take second before first
            this.map.putIfAbsent(first, new HashSet<>());
            this.map.get(first).add(second);
        }

        // calling could take on all course in map:
        for (int course: this.map.keySet()) {
            boolean possible = couldTake(course, new HashSet<>());
            if (!possible) {
                return false;
            }
        }

        return true;
    }
}

621. Task Scheduler

truongductri01 — Thu, 28 Sep 2023 00:22:49 +0000

Problem: 621. Task Scheduler

Observations
With int n is the cooldown time, and char[] tasks is the list of tasks:

We need to pick which task to be conducted during each cycle (within n + 1 units of time)
Within a cycle, the task with the highest frequency should be prioritized to be conducted first.
- > Proof: assume we have tasks = [A, A, B] and n = 1. If we order: B -> A -> idle -> A, the time cost will be 4. while if we order: A -> B -> A, the time cost is only 3.

Implementation:

So, in order to keep track of which task possesses the highest frequency, we will utilize a heap to avoid sorting constantly.

Here is the pseudo-code.

maintain a max heap
while True:
    List<Node> poppedList: used for poping the heap
    Set<Char> visited: used for storing visited characters
    for i = 0 to i = n + 1:
        stop if (the heap is empty and poppedList is also empty)
        pop the root of the heap such that the values are not discovered yet,
        update the frequency and add it poppedList if the freq > 0
        add task to visited

    push the node back into the heap with the updated frequency from poppedList.
    continue until the heap is empty

Solution

class Solution {
    class Node {
        char c;
        int freq;

        public Node(char c, int freq) {
            this.c = c;
            this.freq = freq;
        }
    }

    public int leastInterval(char[] tasks, int n) {
        // count the frequencies of the tasks first
        Map<Character, Integer> taskFreqMap = new HashMap<>();
        for (char t: tasks) {
            taskFreqMap.putIfAbsent(t, 0);
            taskFreqMap.put(t, taskFreqMap.get(t) + 1);
        }

        // then create the heap
        PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> b.freq - a.freq);

        for (char t: taskFreqMap.keySet()) {
            Node newNode = new Node(t, taskFreqMap.get(t));
            pq.add(newNode);
        }


        // start the while loop
        int result = 0;
        while (!pq.isEmpty()) {
            List<Node> popedNode = new ArrayList<>();
            Set<Character> visited = new HashSet<>();

            int idx = 0;
            while (idx < n + 1 && (!pq.isEmpty() || popedNode.size() > 0)) {
                if (!pq.isEmpty()) {
                    Node node = pq.remove();
                    if (!visited.contains(node.c)) {
                        // reduce the frequency 
                        node.freq --;
                        visited.add(node.c);
                    }

                    if (node.freq > 0) {
                        popedNode.add(node);
                    }
                }

                idx ++;
                result ++;
            }

            if (popedNode.size() > 0) {
                for (Node poped: popedNode) {
                    pq.add(poped);
                }
            }
        }

        return result;
    }
}

543. Diameter of Binary Tree

truongductri01 — Sat, 23 Sep 2023 19:56:36 +0000

Problem: 543. Diameter of Binary Tree

First thought:
In order to solve this, we need an important observation: the diameter is the sum of the longest path on the left and right side of any subtree inside the main tree

This tree has a diameter of 6 which is the path [7, 5, 2, 1, 3, 6, 9] or [7, 5, 2, 1, 3, 6, 8]. With [7, 5, 2, 1] is the longest path on the left side of node 1 and 1, 3, 6, 9 is the longest path on the right side of node 1.

Using the same observation, this tree has a diameter of 5 which is the path [7, 5, 3, 2, 4, 6]. With [7, 5, 2] is the longest path on the left side of node 2 and [2, 4, 6] is the longest path on the right side of node 2. This path does not go through the root node since we are not considering the tree with that root as subtree for counting.

Implementation:
We do not need to keep track of the path of every subtree, what we need to keep is the longest path on the left and right side of every node (every subtree in other words). How to do so?

You can spend some time thinking about it and usually, you will find it very complicated to keep track of those numbers without creating a new tree with additional field for each node storing leftLenght and rightLength.

However, we can utilize DFS and recursion to solve this issue. With this approach, we just need to be aware of what we could return after each recursion.
We will return an array of 2 integers. The first element represents the length of the longest path on the left of the node, and the second element represents the length of the longest path on the right of the node.

Here is a simple pseudocode:

start with a node:
int leftRight = new int[2];
- if node has no left and right: 
    pass - nothing to update
- else if:
    if node has left:
        update left side length
        leftRight[0] = max(try with node.left)

    if node has right:
        update right side length
        leftRightArray[1] = max(try with node.right)
- maxValue = max of maxValue and sum of leftRight[0] + leftRight[1];
return leftRight

With this, we just need to keep track of a global variable maxValue to store the final result.

Solution:


class Solution {
    int maxValue = 0;

    public int[] recursion(TreeNode node) {
        // System.out.println("At node: " + node.val);
        int[] leftRight = new int[2];
        if (node.left == null && node.right == null) {
            // nothing happen
        } else {
            if (node.left != null) {
                int[] leftSide = this.recursion(node.left);
                leftRight[0] = Math.max(leftSide[0], leftSide[1]) + 1;
            }

            if (node.right != null) {
                int[] rightSide = this.recursion(node.right);
                leftRight[1] = Math.max(rightSide[0], rightSide[1]) + 1;
            }
        }

        this.maxValue = Math.max(maxValue, leftRight[0] + leftRight[1]);

        return leftRight;
    }

    public int diameterOfBinaryTree(TreeNode root) {
        recursion(root);
        return maxValue;
    }
}

981. Time Based Key-Value Store

truongductri01 — Thu, 21 Sep 2023 00:35:34 +0000

Problem: Time Based Key Value Store

Understanding: This is a fascinating problem requiring us to design a new kind of map/database that could retrieve a key: String by timestamp: int.

The tricky part of the problem is that it requires us to retrieve data of a key such that the return timestamp is less than or equal to the requested timestamp.

For example, if we have a key: foo with the following timestamp: 2: "a", 4: "b", 6: "c". This means that timestamp 2 will be matched with value a, 4 be matched with value b and 6 be matched with value c.

So, if the request is get(foo, 2) we can simply return a. Similarly get(foo, 3) should also return a since 2 is already the closest timestamp to 3.
And if the request is get(foo, 5), that should return b. However, if the request is get(foo, 1), we should return "" since there is no timestamp available that is smaller than or equal to 1.

Matching: We want to match this problem to a DataStructure or Algorithm that we already know

Data Structure: since we want a fast retrieval runtime, HashMap (or dictionary) is the best choice. And in order to retrieve value as map.get(key).get(timestamp), the type of the map should be Map<String, Map<Integer, String>>
Algorithm: there is an interesting find when we look at the input constraints. The timestamp value passed into the set() function will be strictly increased. That means if we keep track of the a list of timestamp, that list will have a strictly ascending order. This simply remind us of Binary Search since we have a sorted array (list).

Implementation

We need to have a map of type Map<String, Map<Integer, String>> as discussed above.

But we also need another map of type Map<String, List<Integer>>. This map will store a list of timestamps connected with a specific key in ascending order. This will be used as source data for binary search.

class TimeMap {
    Map<String, Map<Integer, String>> keyValueMap;
    Map<String, List<Integer>> keyTimeMap;
    public TimeMap() {
        this.keyValueMap = new HashMap<>();
        this.keyTimeMap = new HashMap<>();
    }

    public void set(String key, String value, int timestamp) {
        this.keyValueMap.putIfAbsent(key, new HashMap<>());
        this.keyValueMap.get(key).put(timestamp, value);

        // create a list of time always in ascending order
        this.keyTimeMap.putIfAbsent(key, new ArrayList<>());
        this.keyTimeMap.get(key).add(timestamp);
    }

    private Integer findIndex(String key, int timestamp) {
        // return -1 if we find nothing
        // return i if time at i <= timestamp and time at i + 1 > time 
        // if timestamp < first element in the list => return -1
        // if time stamp >= last element in the list, return the last index 

        // 1. check if the list exist
        if (!this.keyTimeMap.containsKey(key)) {
            return -1;
        }

        // 2. get the list and check the edge case
        List<Integer> timeList = this.keyTimeMap.get(key);
        int left = 0;
        int right = timeList.size() - 1;

        if (timestamp < timeList.get(left)) {
            return -1;
        } else if (timestamp >= timeList.get(right)) {
            return timeList.get(right);
        } else {
            while (left <= right) {
                int middle = (left + right) / 2;

                if (middle <= timeList.size() - 1 && timeList.get(middle) <= timestamp && timeList.get(middle + 1) > timestamp) {
                    return timeList.get(middle);
                } else if (timestamp > timeList.get(middle)) { // lef side is useless
                    left = middle + 1;
                } else if (timestamp < timeList.get(middle)) { // right side is useless
                    right = middle - 1;
                }
            }
            return -1;
        }

    }

    public String get(String key, int timestamp) {
        /**
        Utilize binary search to find a place in the middle of the list in which index i <= time and index i + 1 > time. return i;
        */
        // find the index of the current timestamp 
        int timeValue = this.findIndex(key, timestamp);

        if (timeValue < 0) {
            return "";
        } else {
            return this.keyValueMap.get(key).get(timeValue);
        }
    }
}

/**
 * Your TimeMap object will be instantiated and called as such:
 * TimeMap obj = new TimeMap();
 * obj.set(key,value,timestamp);
 * String param_2 = obj.get(key,timestamp);
 */

Explanation:

The constructor function TimeMap() should be easy to understand since we just initialize the maps needed for our implementation.

Similarly, set() method is just putting elements into the map like we discussed above.

The part that might be a little bit confusing is the findIndex(String key, int timestamp) function which is trying the find the time value that is closest to the requested timestamp.

if there is no existing key stored in our database, return -1. This denoted that there is no valid time value. Else, we have a list variable storing all timestamps value already get put into the database connecting with the key key.
if the value of timestamp is strictly smaller than the first value in list, we can also return -1 since there is no other suitable value.
if the value of timestamp is larger than or equal to the last element in list, we return that last element since that is already the largest value we could possibly get.
otherwise, we can start our binary search. The main go is to find an index i at which list.get(i) <= timestamp and list.get(i + 1) > timestamp. This will shows that list.get(i) is the maximum time value we can get.

For example, assume that we have a request findIndex("foo", 5) and we have an associated list of timestamp connecting with key "foo" is: [1, 2, 3, 4, 6, 7].

start binary search with left = 0 and right = 5.
start 1st while: middle = 2. list.get(2) = 3 This value does not satisfy anything and requires us to ignore anything on the left of middle (anything smaller than index 2). So: left = 3 and start new while loop
start 2st while with left = 3, right = 5: middle = (3 + 5) / 2 = 4. list.get(4) = 6 this also does not satisfy our checks and 6 > 5 so we ignore anything larger than 6. So: right = middle - 1 = 3 and continue the while
start 3rd while with left = right = 3: middle = 3 and list.get(3) = 4. This satisfies our check since list.get(3) = 4 <= 5 and list.get(3 + 1) = 6 > 5. So we return 4. Finally, we just have to return map.get("foo").get(4) as the final result

Missing Numbers

truongductri01 — Wed, 13 Sep 2023 14:20:02 +0000

Problem: here

This is a fascinating problem, which has multiple ways to solve

Several approaches

Sort and find the missing numbers. Simple and easy to implement. O(1) in space and O(n log n) in runtime.
Using HashSet. Put all the numbers in the array into a set. Go through the numbers from 0 to n, if it is not in the set, return that number. Space and time complexity will both be O(n).
Using math. We can easily calculate the sum from 0 to n. Then subtract that with the sum of the elements in the array to get the missing number.
Using some trick of swapping the positions of the elements in the array. (This will be discussed later in this post)
Bit Manipulation (I am not sure about this yet so I will save that for later)

Swapping elements approach to solve this problem

Some observations that we have are:

We have a range from 0 to n, which is n + 1 elements. The array only has n positions (indices). So, in order to conduct the in place element swap, we somehow need to reduce the needed space to only support n elements.
Since the numbers are in range, they will be consecutive, if we sort them, an element with a value i will be in the positions of i - 1 (0-based index).

With these observations, we can remove element 0 from considering for place elements swaps:

We just need to make sure there is already a 0 in the arrays
since if swap 0, we will need index -1, which is not supported (or not good to be used)
Here is a simple explanation of the process:

 /** 
        - swap the positions of the element in place? => will be missing 1 spot
        -> How about we ignore the number 0?
            for each element in the array:
                - if element == index + 1: Continue
                - if element == 0: ignore 
                - else, conduct swap 
                    at index i, we have value val. 
                    swap numbers[i] with numbers[val - 1].
                    Then continue to swap numbers[i] until it matches the value 
        - in the end, go through and check if there is any missing element in the array
        */

class Solution {
    int[] nums;

    public void swap(int idx) {
        int val = nums[idx];

        if (val == idx + 1) return;
        else if (val == 0) return;
        else {
            int temp = nums[val - 1];
            nums[val - 1] = val;
            nums[idx] = temp;
            swap(idx);
        }
    }

    public int missingNumber(int[] nums) {
        this.nums = nums;
        boolean hasZero = false;
        for (int n: nums) {
            if (n == 0) {
                hasZero = true;
                break;
            }
        }

        if (!hasZero) {
            return 0;
        }

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == i + 1) {
                continue;
            } else {
                swap(i);
            }
        }

        // System.out.println(Arrays.toString(this.nums));

        int result = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i + 1) {
                result = i + 1;
                break;
            }
        }
        return result;
    }
}

167. Two Sum II - Input Array Is Sorted

truongductri01 — Wed, 06 Sep 2023 22:16:51 +0000

Problem: here

First approach

Utilize Binary search to conduct search for value needed to make the target sum.

class Solution {
    public int find(int startIdx, int endIdx, int toFind,  int[] numbers) {
        int left = startIdx;
        int right = endIdx;

        while (left <= right) {
            int mid = (left + right) / 2;
            int midValue = numbers[mid];

            if (midValue == toFind) {
                return mid;
            } else if (midValue > toFind) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }

    public int[] twoSum(int[] numbers, int target) {
        /**
        this can be solve with a normal twoSum approach using Map and for loop for a fast O(n) solution.

        Howerver, since this is a sorted array, can we try binary search?


        For i = 0; i < numbers.lenght; i++
            value = numbers[i];
            needToFind = target - value;
            Start finding from (i + 1, numbers.length - 1);
                return > 0 index if found
            simply return that as the result

        Can utilize another map to stored which value has been visited / explored

        => may cost O(n log n) to find the result. 
         */


        int[] result = new int[2];

        for (int i = 0; i < numbers.length - 1; i++) {
            int value = numbers[i];
            int toFind = target - value;

            int idx = find(i + 1, numbers.length - 1, toFind, numbers);

            if (idx > 0) {
                result[0] = i + 1;
                result[1] = idx + 1;
                break;
            }
        }

        return result;
    }
}

This comes with an issue is that we might go through the same value several times using the binary search

Second approach

We can use two pointers to find the wanted target sum

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        /**
        This can be solved with two pointers


        start from left and right
        - if sum > target: move right down
        - if sum < target: move left up
        - else: return the result;

        left and right should never met in the middle.
        */

        int left = 0;
        int right = numbers.length - 1;
        int[] results = new int[2];

        while (left < right) {
            int leftVal = numbers[left];
            int rightVal = numbers[right];
            int sum = leftVal + rightVal;

            if (sum == target) {
                results[0] = left + 1;
                results[1] = right + 1;
                break;
            } else if (sum < target) {
                left ++;
            } else {
                right  --;
            }
        }

        return results;




    }
}

97. Interleaving String

truongductri01 — Fri, 01 Sep 2023 06:48:18 +0000

Problem: Interleaving String

Quick Explanation of the code:

Use Recursion to check all the possibilities of moving forward with the first pointer or the second pointer at each step.
Use DP map to avoid repeated recursion result => reduce runtime

Solution:

class Solution {
    String s1, s2, s3;
    int len1, len2, len3;
    Map<Integer, Map<Integer, Map<Integer, Boolean>>> dpMap;

    public boolean isInDP(int p1, int p2, int p3) {
        if (!dpMap.containsKey(p1)) {
            return false;
        } else {
            if (!dpMap.get(p1).containsKey(p2)) {
                return false;
            } else {
                if (!dpMap.get(p1).get(p2).containsKey(p3)) {
                    return false;
                }
            }
        }
        return true;
    }

    public boolean validate(int p1, int p2, int p3) {
        if (isInDP(p1, p2, p3)) {
            return dpMap.get(p1).get(p2).get(p3);
        }

        boolean newDp = false;

        if (p3 == len3) {
            newDp = true;
        } else if (p1 == len1) {
            boolean isBreak = false;
            while (p2 < len2) {
                if (s2.charAt(p2) != s3.charAt(p3)) {
                    newDp = false;
                    isBreak = true;
                    break;
                }
                p2 ++;
                p3 ++;
            }

            if (!isBreak) {
                newDp = true;
            }
        } else if (p2 == len2) {
            boolean isBreak = false;
            while (p1 < len1) {
                if (s1.charAt(p1) != s3.charAt(p3)) {
                    newDp = false;
                    isBreak = true;
                    break;
                }
                p1 ++;
                p3 ++;
            }
            if (!isBreak) {
                newDp = true;
            }
            // return true;
        } else {
            char c1, c2, c3;
            c1 = s1.charAt(p1);
            c2 = s2.charAt(p2);
            c3 = s3.charAt(p3);

            if (c1 == c2 && c1 == c3) {
                newDp = validate(p1 + 1, p2, p3 + 1) || validate(p1, p2 + 1, p3 + 1);
            } else if (c1 == c3) {
                newDp = validate(p1 + 1, p2, p3 + 1);
            } else if (c2 == c3) {
                newDp = validate(p1, p2 + 1, p3 + 1);
            } else {
                newDp = false;
            }
        }

        dpMap.putIfAbsent(p1, new HashMap<>());
        dpMap.get(p1).putIfAbsent(p2, new HashMap<>());
        dpMap.get(p1).get(p2).put(p3, newDp);

        return newDp;
    }

    public boolean isInterleave(String s1, String s2, String s3) {
        this.s1 = s1;
        this.s2 = s2;
        this.s3 = s3;
        this.dpMap = new HashMap<>();

        len1 = s1.length();
        len2 = s2.length();
        len3 = s3.length();

        if (len3 != len1 + len2) {
            return false;
        }

        return validate(0, 0, 0);
    }
}