DEV Community: So Sun Park

reverse string

So Sun Park — Tue, 01 Aug 2023 01:55:44 +0000

344. Reverse String

Write a function that reverses a string. The input string is given as an array of characters s.

You must do this by modifying the input array in-place with O(1) extra memory.

Relevant problem sets

More challenges
345. Reverse Vowels of a String
541. Reverse String II

Day 7. Singly Linked List

So Sun Park — Thu, 20 Apr 2023 03:01:00 +0000

876. Middle of the Linked List

Given the head of a singly linked list, return the middle node of the linked list.

If there are two middle nodes, return the second middle node.

Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: The middle node of the list is node 3.

Input: head = [1,2,3,4,5,6]
Output: [4,5,6]
Explanation: Since the list has two middle nodes 
with values 3 and 4, we return the second one.

Pseudo Code

something I didn't know was that head.next returns the rest of the values, not the next value.
head = [1,2,3,4,5], head.val = 1, head.next=[2,3,4,5]

var middleNode = function(head) {
    // check the total length of initial ListNode
    // middle index is totalLen/2
    // get the ListNode from middle to the end

    // console.log(head, head.val, head.next)
    // head: val ~ rest
    // head.val : val only
    // head.next: rest only (no val included)
}

var checkLength = function(head) {
    // init counter
    // until current value is null OR
    // until there's no more next, increment the counter
    // return the counter
}

My Attempt

Things about ListNode (different from Array)

You cannot access the length of the entire nodelist, so we need to traverse the entire ListNode and increment the counter
Be mindful about the LinkedList definition given in the problem set
Be mindful of while loop condition(when to stop the counter), especially inside checking the length function.

// Definition for singly-linked list.
function ListNode(val, next) {
  this.val = (val===undefined ? 0 : val)
  this.next = (next===undefined ? null : next)
}


/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var middleNode = function(head) {
    let totalLen = checkLength(head);
    let mid = ~~(totalLen/2);  
    // ~~: same as Math.floor, but efficient
    let counter = 0;
    while(counter < mid) {
        head = head.next; // update to next ListNode
        counter += 1;
    }
    return head;

};

var checkLength = function(head) {
    let counter = 1;
    // start with 1 because
    // while loop ends before counting the last element, 
    // which has null as next
    while(head.next !== null) { 
        counter += 1;
        head = head.next;
    }
    return counter;
}

Improve

So I kind of got caught up with the fact that this is singly linked list and didn't think too much about two pointers theme.
There seems to be much simpler way to solve this.

Array
two pointers: slow and fast

Relevant problem sets

2095. Delete the Middle Node of a Linked List
2130. Maximum Twin Sum of a Linked List

Day 6. Reverse String problems (two pointers)

So Sun Park — Wed, 19 Apr 2023 05:41:30 +0000

We cannot directly swap characters and change in-place with Javascript string, just like we did for array of characters.
- why? Because String is immutable
We cannot directly assign a letter via index to an empty string. you need to use + operation to write on the string.

First Attempt Code

// string => array => swap => string
var reverseWords = function(s) {
    let words = s.split(" ");
    for(let i = 0; i < words.length; i++) {
        words[i] = swap(words[i]);
    }
    return words.join(" ");
};

var swap = function(word) {
    let chars = word.split('');
    let leftP = 0;
    let rightP = chars.length - 1;
    while(leftP < rightP) {
        if(chars[leftP] !== chars[rightP]) {
            let leftChar = chars[leftP];
            chars[leftP] = chars[rightP];
            chars[rightP] = leftChar;
        }
        rightP--;
        leftP++;
    }
    return chars.join('');
}

Improved version

/**
 * @param {string} s
 * @return {string}
 */

// improved version of swap function above
function reverseString(s){
    let arr = s.split('');
    let length = ~~(arr.length/2);
    for(let i = 0; i< length; i++){
        [arr[i],arr[s.length-1-i]] = [arr[arr.length-1-i],arr[i]];
    }
    return arr.join('');
}
var reverseWords = function(s) {
    let arr = s.split(' ');
    for(let i = 0; i<arr.length; i++){
        arr[i] = reverseString(arr[i]);
    }
    return arr.join(' ')
};

Second Way

I was trying to think of a way to stick with two pointers, but at the end, it doesn't seem to different.
This is not too different from the first way, except that here I didn't separate the works. From clean code perspective, it would be better to take out content of while loop as separate function outside.
Maybe in javascript, first way could be better or similar to this second method.

var reverseWords = function(s) {
    let wordStart = 0; 
    let wordEnd = 1;
    let newWords = [];

    while(wordEnd <= s.length) {

        // hits the space or end
        if(wordEnd === s.length || s[wordEnd] == ' ') {
          // extract word and reverse
          let word = s.substring(wordStart, wordEnd);
          let reverseWord = "";
          // add char from the end of substring
          for(let i = word.length - 1; i >= 0; i-- ) {
            reverseWord += word[i];
          }
          newWords.push(reverseWord);
          // update wordStart to a beginning of next word
          wordStart = wordEnd + 1;
        }
        // increment wordEnd index until it hits the space or end
        wordEnd++;
    }
    // console.log(newWords);
    return newWords.join(" ");
};

Python solution

just interesting

class Solution:
    def reverseWords(self, s: str) -> str:
        return " ".join([word[::-1] for word in s.split()])

~~ operator

In JavaScript, ~~ is a bitwise operator that performs a double bitwise NOT operation.

The double bitwise NOT operator converts its operand to a signed 32-bit integer. It is equivalent to Math.floor() for non-negative numbers and Math.ceil() for negative numbers.

For example, ~~3.14 returns 3, and ~~(-3.14) returns -3.

The ~~ operator can be used as a faster alternative to Math.floor() or parseInt() in certain situations where you only need to convert a positive number to an integer. However, it should be used with caution as it can produce unexpected results for negative numbers or non-numeric inputs.

Relevant problem set

541. Reverse String II

Previous Challenge 344. Reverse String

Write a function that reverses a string. The input string is given as an array of characters s.

You must do this by modifying the input array in-place with O(1) extra memory.

Relevant problem sets
More challenges
345. Reverse Vowels of a String
541. Reverse String II

Day 5. two sum with two pointers

So Sun Park — Tue, 18 Apr 2023 03:01:04 +0000

Problem Set

167. Two Sum II - Input Array Is Sorted

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

first attempt

use two pointers
increment both from left side
rightP is always same or bigger than leftP+1
when I can't find matching rightP for the target, increase the leftP+1 and update rightP starting value as well (rightP = leftP + 1)

Pseudo code

1. leftP = 0, rightP = leftP+1
2. first loop: leftP increments from 0 to numbers.length - 2
3. for each leftP, find rightP from the rest of the array. 
4. second loop: rightP starts from leftP+1, and checks until the end of array. 
5. if sum = target, return
6. if sum != target, keep increasing rightP
7. if you don't find any, increase leftP++ and repeat another round.

Problem

time limit exceeded
it is inefficient. almost like a double for loop.

Solution

How to make a better use of two pointers?
Use non-decreasing order array wisely
It means smaller value is on left, bigger value is on right
Let's start pointers from the other ends, not adjacent (next to each other)
We can check the sum of two pointers and compare with the target

1. if sum > target, the sum has to decrease. So move the rightP(bigger value positions) to left(--)
2. if sum < target, the sum has to increase. So move the leftP(smaller value positions) to right(++)

This reduces the amount of pointers movement and loops very significantly.

Helpful links

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/solutions/2128501/two-pointers-visual-explanation-java/?envType=study-plan&id=algorithm-i

Relevant problem sets

653. Two Sum IV - Input is a BST
1099. Two Sum Less Than K

Day 4. two pointers - move zero(es) to the end of array

So Sun Park — Mon, 10 Apr 2023 07:12:19 +0000

Now I'm more used to remind myself of two pointers, I tried not to look at solutions or other people's posts. And I made it without looking them up!

283. Move Zeroes

Description: Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements. Note that you must do this in-place without making a copy of the array.

Example 1:
Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

Example 2:
Input: nums = [0]
Output: [0]

Learning points

I initially just tried the easy JS way, using unshift and push methods. But it led to out of memory.
do I want to count the total number of zero and use it somehow? how to replace the original zero spot with non-zero? how to swap non-zero and zero?
I kind of thought of #2 approach in the editorial post, counting the number of zeroes and fill at the end of array. But I didn't think too deep and thought it may not be two pointers. But the explanation made sense.

Editorial post explanation. good

This is a 2 pointer approach. 
The fast pointer which is denoted by variable "cur" 
does the job of processing new elements. If the newly 
found element is not a 0, we record it just after the
 last found non-0 element. The position of last found 
non-0 element is denoted by the slow pointer 
"lastNonZeroFoundAt" variable.

Attempts

1. Initial JS unshift, push methods

// solution 1: unshift, push, O(n) for loop
// Runtime error: JS heap out of memory
for(let i = 0; i < nums.length; i++) {
    if(nums[i] == 0) {
        nums.unshift();
        nums.push(0);
    }
}

2. Next pseudo-code idea process with two pointers

move all the zeroes to the front.
reverse the entire array. [0, 0, 0..] would go to the end of array.
reverse non-zero partial array only. [12, 10, 3, 1] to [1, 3, 10, 12]
(I was maybe caught up with reverse/rotate idea because I just finished that quiz right before this lol)
I realized that [1, 2, 3, 0, 0, 4, 5] this test case still wouldn't work with the current idea.

3. Better idea process with two pointers

Putting the zeroes to the front, and then reverse blah blah, which already seems complicated than it should be.
I thought there should be a way to simplify this.
I tried to use two pointers to swap non-zero and zero to move the zeroes to the latter index, not to the front.

Codes

Final Pseudo code

lower, upper pointers: start from index 0, 1
compare nums[lower] and nums[upper]
if nums[lower] is 0, nums[upper] is non-zero, we swap and put non-zero to the front. Then, we increase both pointers by 1: lower++, upper++
if nums[lower] and nums[upper] are both 0, we don't swap. We only increase upper+1 to find next non-zero.
if nums[lower] and nums[upper] are both non-zero, we need to find next zero & non-zero combinations. So we increase both pointers by 1: lower++, upper++

At first, I missed the #5 point, so it returned time limit exceeded error.

Final code

let lower = 0;
let upper = lower + 1;
while(upper < nums.length) {
    if(nums[lower] == 0 && nums[upper] == 0) {
        // increment p2 only to find non-zero element
        upper++;
    } else {
        if(nums[lower] == 0 && nums[upper] != 0) {
            // swap non-zero and zero 
            let non_zero = nums[upper];
            nums[upper] = 0;
            nums[lower] = non_zero;
        } 
        // increment both pointers
        // when one or both are non-zero
        lower++;
        upper++;
    } 
}

Solution 2 of editorial post

void moveZeroes(vector<int>& nums) {
    int lastNonZeroFoundAt = 0;
    // If the current element is not 0, then we need to
    // append it just in front of last non 0 element we found. 
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] != 0) {
            nums[lastNonZeroFoundAt++] = nums[i];
        }
    }
    // After we have finished processing new elements,
    // all the non-zero elements are already at beginning of array.
    // We just need to fill remaining array with 0's.
    for (int i = lastNonZeroFoundAt; i < nums.size(); i++) {
        nums[i] = 0;
    }
}

Relevant problems or quizzes

Day 3. Two pointers - rotate array

So Sun Park — Mon, 10 Apr 2023 05:44:23 +0000

While the topic of this problem is clearly stated as two pointers, as I got obsessed with the question itself, I forgot the core idea or approaches. So I had to refer to some of the posts to realize how I can use two pointers to approach this problem.

189. Rotate Array

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Learning points

I get how reverse all, reverse first part, reverse the other part approach works the best. But still in the process of understanding how to come up with an idea from the first place hmm...
For all 3 types of solutions, a remainder operation for k is the key to solve the cases in which k > nums.length.

if(k > nums.length) {
  k = k % nums.length;
}

Initial attempts

Without k%nums.length operation, the solution 2 didn't work for nums=[1,2], k = 5 test case.
solution 1 works fine, but when I submitted, it showed time limit exceeded - even with k%nums.length operation.

Solution 1

    if(k > nums.length) {
        k = k % nums.length;
    }
    for(let i = 0; i < k; i++) {
        // pop from last index
        let last = nums.pop();
        // insert to first index
        nums.unshift(last);
    }

Solution 2

    if(k > nums.length) {
        k = k % nums.length;
    }
    let k_nums = nums.slice(nums.length - k, nums.length); 
    // slice: returns new array of start ~ end-1 
    // splice: delete original array from start ~ end-1

    // O(n)
    for(let i = k_nums.length - 1; i >= 0; i--) {
        let n = k_nums[i];
        nums.unshift(n);
    }

For solution 2, I first attempted to slide (make a new array of last k items - [4, 5, 6] ), splice (delete k items from the original - [0, 1, 2, 3] ) and then concat. Then I tried to do nums = a result of concat [4, 5, 6, 0, 1, 2, 3].
But because the leetcode question was asking to modify the nums - the original array, it didn't work.
So I had to find another way to modify the nums. Here, I used unshift with for loop to add [4,5,6] in backwards order to the beginning of spliced array [0, 1, 2, 3].

Final code

var reverse = function(nums, lower, upper) {
    while(lower < upper) {
        let temp = nums[lower];
        nums[lower] = nums[upper];
        nums[upper] = temp;

        lower++;
        upper--;
    }
}
var rotate = function(nums, k) {
    // solution 3: FINAL
    // reverse the entire array
    reverse(nums, 0, nums.length - 1);
    if(k > nums.length) {
        k = k % nums.length;
    }
    // reverse first half array
    reverse(nums, 0, k - 1);
    // reverse last half array
    reverse(nums, k, nums.length - 1);
};

Helpful posts

Replace Math.floor() into >>> shift operation in JS for optimization

So Sun Park — Sun, 09 Apr 2023 08:27:08 +0000

Thanks to Tony B's comment on my Leetcode blogging post, I got to look up again on shift operators in Javascript.
Love the community's feedback. One more reason to post my progress and studies :P

mid = Math.floor((lower + upper) / 2);

Above can be changed to below.

mid = lower + ((upper - lower) >>> 1);

// or this

mid = (lower + upper) >>> 1;

Quick Note
Regarding the basic mathematical equation of getting the middle number of two different numbers, lower + (upper-lower)/2 is as same as (lower + upper)/2.

Learning points

Math.floor() is not very optimized operation.
What is & How to use >>> shift operation
Exception: >>> operation does not work for BigInt.

Disclaimer: I got some help of ChatGPT to get these explanations.

How come is this replaceable / possible?

The >>> (zero-fill right shift) operator in JS is often used as an optimization technique to perform integer division by a power of 2, effectively achieving the same result as dividing by 2 (or any power of 2).
The reason this works is because bitwise operators in JS operate on 32-bit signed integers, which are represented in two's complement format. In two's complement, the leftmost bit (the sign bit) is used to represent the sign of the number, with 0 indicating positive and 1 indicating negative. The remaining 31 bits represent the magnitude of the number.
When you use the >>> operator to shift the bits of a positive integer to the right by 1 position, you are effectively dividing the number by 2 and rounding down to the nearest integer. This is because shifting the bits to the right by 1 position is equivalent to dividing the number by 2, and the >>> operator fills the vacated leftmost bit with 0, which ensures that the result is always a non-negative integer.
Using >>> 1 is effectively equivalent to dividing by 2 and rounding down, providing an optimized way to achieve integer division by a power of 2.

let num = 10;
let result = num >>> 1;
console.log(result); // Output: 5

/**
The binary representation of 10 is 
00000000000000000000000000001010. 

Shifting the bits to the right by 1 position using >>> gives 
00000000000000000000000000000101

which is equivalent to the decimal value 5.
**/

Why is Math.floor() operation inefficient compared to bit shift operation?

Floating-point arithmetic: Math.floor() operates on floating-point numbers, which are represented with decimal points and can have fractional parts. Performing floating-point arithmetic can be computationally more expensive compared to integer arithmetic, as it involves additional steps for handling the fractional parts and rounding.
Type coercion: Math.floor() returns a floating-point number, which may require type coercion to convert it to an integer if an integer result is desired. Type coercion can introduce additional overhead in terms of performance and code readability.
Potential loss of precision: Floating-point numbers in JavaScript have limited precision, which means that very large or very small numbers may lose precision due to the limitations of the floating-point representation. This can result in subtle rounding errors or inaccuracies when working with large numbers.

Why is >>> operation more efficient?

The >>> operator in JavaScript performs bitwise operations on 32-bit signed integers, which do not involve floating-point arithmetic and can operate more efficiently at the binary level.
The >>> operator fills the vacated leftmost bit with 0, ensuring that the result is always a non-negative integer, which can provide better accuracy and consistency for integer division.

Also, chatGPT added, saying

However, it's worth noting that modern JavaScript
engines are highly optimized and the performance 
difference between these two methods may not be 
significant in most practical scenarios. 

It's always recommended to profile and benchmark 
your code to determine the actual performance 
impact in your specific use case.

P.S.
I remember learning such bit operations and concepts during college CS classes. I took 'Operating Systems' class in undergrad - a great class taught by Professor Jason Waterman. In the beginning of the class, it was very tough, especially debugging the assembly code... But at the end, it really helped me to understand why programming languages are made like this and how computers actually work under the hood when I type and compile the programming.

I think I was probably one of the only few junior/senior students who were not majoring/minoring in CS back then. After I got into VR, I realized I wanted to study more computers. Thus, I later wanted to minor in CS, but it was quite late to take all the required classes. While I feel more and more confident with my programming skills and experiences as I work, I kind of wished I minor/majored in CS, especially whenever I see all those JD saying 'computer science degree' :'( But oh well, gotta just keep going !!

Day 2 - Two pointers O(n)

So Sun Park — Sat, 08 Apr 2023 12:52:07 +0000

Question: 977. Squares of a Sorted Array

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

Follow up

Squaring each element and sorting the new array is very trivial, could you find an O(n) solution using a different approach?

Example 1:

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].

Example 2:

Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]

First attempt: using bubble sort

My initial thought was 'do I have to sort this before or after squaring each number? which sort method would be efficient?'
To make it less than O(N2), it seemed like I have use heap sort. But heap sort still is not O(N), which follow-up question prefers. It is O(n*logn).
For here, though I knew that bubble sort is O(N2), I just wanted to practice bubble sort, which is one of the simple sorts we usually first learn.

Second attempt: using two pointers and aim O(N)

It seemed like I can take an advantage of non-decreasing order.
I tried to think of ways, asking how to move a negative number or its squared value to the correct position?
It seemed like I had to compare the value of square(positive num) vs. square(negative num)
I also referred to this post at the end to refine my solution.
In this solution, it adds bigger squared(value) to a beginning of result array. And then reverse the result array at the end to make it *non-decreasing order.
In my solution, I started adding squared(value) from the end of result array. And then make it to its index 0.
Here, I first thought I can use upper_index as and index for adding new item to result array. But two different conditional cases returned different outcomes. So I created last_index variable to be clear and working for both cases.

Psuedo code

var sortedSquares = function(nums) {
    // 2. O(n) with two pointers
    // #1. if all nums are positive, just return simple squared result.

    // #2. if there's negative nums, we need two pointers leftmost, rightmost
    // similar to binary search two pointers.
    // compare two pointers' squared values
    // and add bigger number to the end of the list, aka at upper_bound index.
    let lower_bound = 0;
    let upper_bound = nums.length - 1;
    let reordered_arr = [];
    while(lower_bound <= upper_bound) {
        // if lower val is bigger than upper val
        // add lower(bigger) val to upper index of new arr
        // move lower index + 1

        // if upper val is bigger than lower val
        // add upper(bigger) val to upper index of new arr
        // move upper index - 1

    }
    return reordered_arr;

};

Final code

var sortedSquares = function(nums) {
    // 2. O(n) with two pointers
    // #1. if all nums are positive, just return simple squared result.
    let has_negative = false;
    for(let i = 0; i < nums.length; i++) {
       if(nums[i] < 0) {
           has_negative = true;
           break;
       }
    }
    if(!has_negative) {
        let squared_arr = [];
        for(let i = 0; i < nums.length; i++) {
            squared_arr.push(nums[i]*nums[i]);
        }
        return squared_arr;
    }
    // #2. if there's negative nums, we need two pointers leftmost, rightmost
    let lower_bound = 0;
    let upper_bound = nums.length - 1;
    let reordered_arr = [];
    let last_index = upper_bound;
    while(lower_bound <= upper_bound) {
        if(nums[lower_bound]*nums[lower_bound] >= nums[upper_bound]*nums[upper_bound]) {
            reordered_arr[last_index] = nums[lower_bound]*nums[lower_bound];
            lower_bound += 1;
        } else if(nums[upper_bound]*nums[upper_bound] > nums[lower_bound]*nums[lower_bound]) {
            reordered_arr[last_index] = nums[upper_bound]*nums[upper_bound];
            upper_bound -= 1;
        }
        last_index -= 1;
        // i initially put the squared num to [upper_bound] index, but it messes the insertion.
        // using last_index is more clear
    }
    return reordered_arr;
};

Day 1 - binary search

So Sun Park — Sat, 08 Apr 2023 12:28:09 +0000

This problem set is under 'Binary Search' of 'Algorithm 1' section of '14 days Study plan of algorithm'.

Question 35. Search Insert Position

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

Learning points

It is based on binary search method.
The trick is return the index where it is supposed to be inserted.
In the first attempt, I was confused what variable to use in order to calculate the supposed index
All the cases when target is not found, lower_bound is always bigger than upper_bound. (take a look at while condition again.)
I tried to divide if/else case for lower_bound > nums.length or upper_bound < 0
But it turns out, that is neither necessary nor efficient.
Returning lower_bound index is enough for all such cases.

Final code

var searchInsert = function(nums, target) {
    let lower_bound = 0;
    let upper_bound = nums.length - 1;
    let mid;

    while(lower_bound <= upper_bound) {
        mid = Math.floor((lower_bound + upper_bound) / 2);
        if(nums[mid] < target) {
            lower_bound = mid + 1;
        } else if(nums[mid] > target) {
            upper_bound = mid - 1;
        } else if (nums[mid] == target) {
            return mid;
        }
    }
    return lower_bound;
}

Hands-on example

Let us say we have [1, 3, 5, 6]
1. when target = 0
2. when target = 2
3. when target = 7

1. target = 0, nums = [1, 3, 5, 6]

1st while loop:
- lower: 0
- upper: 3
- mid: (0+3)/2 = Math.floor(1.5) = 1
- nums[mid] > target: move upper down to mid - 1
- upper is updated: 0

2nd while loop: 
- lower: 0
- upper: 0
- mid: (0 + 0)/2 = Math.floor(0) = 0
- nums[mid] > target: move upper down to mid - 1
- upper is updated: -1

3rd while loop
- Breaks because it's no longer lower <= upper

Outside while, we have...
- lower: 0
- upper: -1
- mid: 0
- Our target(0) should be located at index 0. 
In this case, it seems like
we can use either lower or mid index

2. target = 2, nums = [1, 3, 5, 6]

1st while loop:
- lower: 0
- upper: 3
- mid: (0+3)/2 = Math.floor(1.5) = 1
- nums[mid] > target: move upper down to mid - 1
- upper is updated: 0

2nd while loop: 
- lower: 0
- upper: 0
- mid: (0 + 0)/2 = Math.floor(0) = 0
- nums[mid] < target: move lower up to mid + 1
- lower is updated: 1

3rd while loop
- Breaks because it's no longer lower <= upper

Outside while, we have...
- lower: 1
- upper: 0
- mid: 0
- Our target(2) should be located at index 1. 
In this case, it seems like
we can only use lower index as a return value.

Now, next case will help us to decide which variable we should use as our answer.

3. target = 7, nums = [1, 3, 5, 6]

1st while loop:
- lower: 0
- upper: 3
- mid: (0+3)/2 = Math.floor(1.5) = 1
- nums[mid] < target: move lower up to mid + 1
- lower is updated: 2

2nd while loop: 
- lower: 2
- upper: 3
- mid: (2+3)/2 = Math.floor(2.5) = 2
- nums[mid] < target: move lower up to mid + 1
- lower is updated: 3

3rd while loop
- lower: 3
- upper: 3
- mid: (3+3)/2 = 3
- nums[mid] < target: move lower up to mid + 1
- lower is updated: 4

4th while loop
- Breaks because it's no longer lower <= upper

Outside while, we have...
- lower: 4
- upper: 3
- mid: 3
- Our target(7) should be located at index 4. 
In this case, it seems like
we can only use lower index as a return value.

Thus, we can safely assume, what we need to care is lower_bound index at the end.

mouse click, down, up

So Sun Park — Thu, 09 Mar 2023 09:13:59 +0000

when you click with your mouse, mouse events fire in this order.

down, up, click.

which is counter-tuitive to humans clicking behavior.

down, click, up.

So when you try to set some boolean values to via down, up events and fire certain feature/event on mouse-click, be careful.

html img, blob, base64

So Sun Park — Thu, 09 Mar 2023 01:30:54 +0000

problem

upload image via <input>
inject that file into <img src="">
src url is blob url
when i try to copy this src: blobUrl into another <img src=""> tag, it throws file not found error bc the image is not saved in server.

solution

when upload the image, use FileReader() API
convert the uploading-image into base64 string with readAsDataURL()
inject that base64string into <img src="">
now you can take that src to any other <img src=""> tags

https://refine.dev/blog/how-to-base64-upload/

mobile touch event listeners

So Sun Park — Wed, 22 Feb 2023 08:11:32 +0000

https://developer.mozilla.org/en-US/docs/Web/API/Touch/clientX

https://www.uriports.com/blog/easy-fix-for-unable-to-preventdefault-inside-passive-event-listener/

https://developer.mozilla.org/en-US/docs/Web/API/Element/touchmove_event

DEV Community: So Sun Park

reverse string

Relevant problem sets

Day 7. Singly Linked List

876. Middle of the Linked List

Pseudo Code

My Attempt

Improve

Relevant problem sets

Day 6. Reverse String problems (two pointers)

First Attempt Code

Improved version

Second Way

Python solution

~~ operator

Relevant problem set

Day 5. two sum with two pointers

Problem Set

first attempt

Helpful links

Relevant problem sets

Day 4. two pointers - move zero(es) to the end of array

283. Move Zeroes

Learning points

Attempts

Codes

Relevant problems or quizzes

Day 3. Two pointers - rotate array

189. Rotate Array

Learning points

Initial attempts

Final code

Helpful posts

Related problems / quizzes

Replace Math.floor() into >>> shift operation in JS for optimization

Learning points

How come is this replaceable / possible?

Why is Math.floor() operation inefficient compared to bit shift operation?

Why is >>> operation more efficient?

Day 2 - Two pointers O(n)

Question: 977. Squares of a Sorted Array

Follow up

First attempt: using bubble sort

Second attempt: using two pointers and aim O(N)

Psuedo code

Final code

Similar algorithm problems

Day 1 - binary search

Question 35. Search Insert Position

Learning points

Final code

Hands-on example

1. target = 0, nums = [1, 3, 5, 6]

2. target = 2, nums = [1, 3, 5, 6]

3. target = 7, nums = [1, 3, 5, 6]

mouse click, down, up

html img, blob, base64

problem

solution

mobile touch event listeners