DEV Community: ShangjieZhou

JS: Closure

ShangjieZhou — Mon, 06 May 2024 04:32:51 +0000

1. What is closure

A combination of a function and the environment the within which that function was declared. For example:

function makeFunc() {
  const name = "Mozilla";
  function displayName() {
    console.log(name);
  }
  return displayName;
}

const myFunc = makeFunc();
myFunc();

The closure here is the combination of function displayName and the variable name. Therefore, function displayName remains a reference to variable name, and when later myFunc is invoked, it'll be be able to access the variable name hence print out Mozilla.

Closures in JavaScript capture variables by reference, not by value, which means if the value of the lexical environemtn variable changes, it will be reflected inside the function. For example:

myFunctions = []

let i = 0;
while (i < 3) {
  const a = () => console.log(i);
  myFunctions.push(a);
  i += 1;
}

for (let f of myFunctions) {
  f();
}

2. Using closure for private methods

We can utilise JS closure to write encapsulated functions and variables that are inaccessable outside an object and to expose functions and variables to outer environments, like private and public methods in Java:

const makeCounter = function () {
  let privateCounter = 0;
  function changeBy(val) {
    privateCounter += val;
  }
  return {
    increment() {
      changeBy(1);
    },

    value() {
      return privateCounter;
    },
  };
};

const counter = makeCounter();
console.log(counter.value()); // 0.
counter.increment();
console.log(counter.value()); // 1.

which is equivalent to the Java code below:

public class Counter {
    private int privateCounter = 0;

    private void changeBy(int val) {
        privateCounter += val;
    }

    public void increment() {
        changeBy(1);
    }

    public int value() {
        return privateCounter;
    }
}

3. Closure within closure

The following code will not behave as expected:

function showHelp(help) {
  document.getElementById("help").textContent = help;
}

function setupHelp() {
  var helpText = [
    { id: "email", help: "Your email address" },
    { id: "name", help: "Your full name" },
    { id: "age", help: "Your age (you must be over 16)" },
  ];

  for (var i = 0; i < helpText.length; i++) {
    var item = helpText[i];
    document.getElementById(item.id).onfocus = () => showHelp(item.help);
  }
}

But changing the declaration of item from var to const will work, since now in every loop a new variable is created with the updated value:

for (let i = 0; i < helpText.length; i++) {
    const item = helpText[i];
    document.getElementById(item.id).onfocus = () => {
      showHelp(item.help);
    };
  }

Or we can keep the var, but using yet another closure to capture the variable's live value within each loop by creating another inner function:

function showHelp(help) {
  document.getElementById("help").textContent = help;
}

function makeHelpCallback(help) {
  return function () {
    showHelp(help);
  };
}

function setupHelp() {
  var helpText = [
    { id: "email", help: "Your email address" },
    { id: "name", help: "Your full name" },
    { id: "age", help: "Your age (you must be over 16)" },
  ];

  for (var i = 0; i < helpText.length; i++) {
    var item = helpText[i];
    document.getElementById(item.id).onfocus = makeHelpCallback(item.help);
  }
}

The 0/1 Knap-sack Problem

ShangjieZhou — Thu, 29 Feb 2024 05:53:50 +0000

1. Overall Idea

The sub-problem:
If we're given the optimal solution for item[0]...item[i] with a bag of size n, when facing item[i+1], we only have to think about two things:

If we must add item[i+1] of weight[i+1] and value[i+1], then the total value is: (optimal solution for item[0]...item[i] with a bag of size n-weight[i+1]) + (value[i+1])
See if not including item[i+1] yields a higher value, in other words, check optimal solution for item[0]...item[i] with a bag of size n

Therefore, it's clear to see that we define the sub-problem as a two-dimension memoization, where:

dp[i][j] = the optimal solution for the first i items with a bag of size j
dp[i][j+1] = the higher of dp[i-1][j+1] and dp[i-1][j-weight[i]] + value[i]

2. The Classic Approach

We first init a 2D array, where row[i] = item[i] and col[i] = bag of size i.

Populate the base cases of "empty bag with all items" and "first item with bag of all sizes"

dp = int[item_len][bag_size + 1]
for i in range(0, item_len): 
    dp[i][0] = 0
for i in range(0, bag_size + 1): 
    dp[0][i] = values[0] if i >= weights[0] else 0

Applying the sub-problem induction logic, note that we need to start from the second row and second column in each row.

for i in range(1, item_len):
    for j in range(1, bag_size + 1):
        if weights[i] > j: # item too big
            dp[i][j] = dp[i - 1][j]
        else:
            add_item = dp[i - 1][j - weights[i]] + values[i]
            skip_item = dp[i - 1][j]
            dp[i][j] = max(add_item, skip_item)

Space Complexity: O(bag_size * item_len)
Time Complexity: O(bag_size * item_len)

3. Space-Optimised Approach

In the previous approach, we used a 2D array to store the computed results in our DP but we can observe one thing that to compute the result for item[i] we just need the results for item[i-1].

Therefore, we can reduce the size of our DP to 1D by just storing the results on different bag sizes for the previous element.

dp = [0] * (bag_size + 1)
for i in range(0, bag_size + 1):
    if weights[0] <= i: dp[i] = values[0]

for i in range(1, size):
    for j in range(1, bag_size + 1):
        if weights[i] > j:
            dp[j] = prev[j]
        else:
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])

print(memo[bag_size])

Space Complexity: O(bag_size)
Time Complexity: O(bag_size * item_len)

4. The "Forward-Thinking" Approach (Intuitive)

In all previous approaches, we think in the way of "if I add the current item(of weight w) into my bag(of size n), I must trace back to find the optimal solution for bag size of n-w in order to calculate the new total value".

This is a form of back-tracking, using "backward thinking".

Another way to think about this could be "if I add the current item(of weight w) into my bag(of size n), it will produce a new solution(not necessarily optimal) for bag size of n+w, given the optimal solution for bag size of n"

This is more like "forward-thinking", which is actually just the same logic, but we will now use a hashmap instead of an array to store the intermediate results, and each key-value pair of the hashmap now has a slightly different meaning than the array approach:

each key of the hashmap is an integer in range [0, bag_size]
each value of key n marks the optimal solution for a bag that has items with total size of exactly n

# an empty bag has maximum value of 0
dp = {0: 0}

for i in range(0, item_len):
    prev = dict(dp)
    for size in prev:
        new_size = size + weights[i]
        if new_size <= bag_size:
            if new_size in prev:
                dp[new_size] = max(prev[new_size], prev[size] + values[i])
            else:
                dp[new_size] = prev[size] + values[i]

print(max(dp.values()))

Note that we cannot simply return dp[bag_size] as the final solution with this approach, since:

There might not be a combination of items that gives a total weight of exactly bag_size
The optimal solution might come from a key that is less than bag_size

Space Complexity: O(bag_size)
Time Complexity: O(bag_size * item_len)

5. The Target Sum Problem

Given an array of positive integers nums, and an integer target, return True if there is a subset of nums such that the sum of its elements is equal to target, return False otherwise.
Example: nums = [1,2,3,3], target = 7 will return True ([1,3,3])

We could solve this problem with the classic knap-sack approach, where target is the bag size, and each number x in nums can be regarded as an item of weight x and value x, then at the end we simply return dp[target] == target

dp = [False] * (target + 1)
dp[0] = True

for num in nums:
    for i in range(num, target + 1):
        dp[i] = dp[i] or dp[i - num]

return dp[target_sum]

However, it's also interesting to follow the "forward thinking" approach:

we loop through each number in nums
at each number n, we keep a list of all possible sums so far sums, and add in the new sums produced by n+sums[i]

An example using hashmap

possible_sums = {0: True}

for n in nums:
    prev = dict(possible_sums)
    for s in prev:
        if s + n <= target: possible_sums[s + n] = True

return (target in possible_sums)

Note that the only difference here is that we change the order in which to find the solution, from "looking back" to "looking forward". However, by turning it to "forward thinking", it now feels more linear and straight forward.

I often find it useful to take the "forward-thinking" approach for many other knapsack-like problems.

Conclusion

In this blog, I compared the classic approach, space-optimised approach and forward-thinking approach of solving the 0/1 knap-sack problem, as well as showing how the forward-thinking approach could give us another subtle way to view and understand the knap-sack problem, by solving another similar problem "Target Sum".

All of these approaches are essentially the same strategy using dynamic programming, but I hope that by giving a side-by-side comparison here, it can help us build a more thorough understanding of the knapsack problem and the idea behind dynamic programming.

Leetcode Notes

ShangjieZhou — Sat, 02 Dec 2023 06:29:37 +0000

797. All Paths From Source to Target

Use recursion to find all possible paths from the source node to the destination node.
A few important things to think about when writing recursion algorithms:

How to define the recursion function: what to accept as input, what to return (maybe no return value, but instead modifying global variables at each recursion)?
The scope of each recursion: what's the responsibility at each recursion? For example, do we append the child nodes at this recursion, or leave it to the next recursion? i.e. only append the current node at this recursion, or only append the child nodes? Note that this will affect how we define base case as well.
The base case/end of recursion: sometimes the base case is implicitly executed when looking at the next step in the current recusion.

200. Number of Islands

Combine 2D array traversal + BFS to determine the number of isolated graphs.

When approaching a problem, don't restrict yourself to only one algorithm. Like in this case, it's a combination of array traversal and BFS.
Try to think without specific algorithm technique first, but to first come up with a high level strategy, to make some observations, then think of the specific realisation of it.

695. Max Area of Island

Very similar to the problem above.

Again, one crucial thing when doing recursion is to be very clear about what each recursion does. In this example, there's 2 alternatives:

Add the area of child nodes each recursion
Add the area of the current node

151. Reverse Words in a String

The take away message is to utilise the idea of "global reverse" + "partial reverse", which is useful for many in-place string manipulation problems.

Greedy

The idea is "each step we will not miss the global optimal solution"
Validity often supported by "proof by contradiction"
When to use? It's by intuition and trials and errors really...

134. Gas Station

-- make close observations when planning each greedy step.

A typical greedy solution would use 2 pointer method: both start from index 0, curr goes clockwise while base goes anti-clockwise. Whenever the currentSum is < 0, meaning out of gas, we move base anti-clockwise by 1 index. The loop terminates when the 2 pointers intersect (together complete a whole circle)

The key observation here is, whenever the currSum between i and i + n is negative, any base starting between [i, i + n] would also result in negative currSum, but position i - 1 might give us extra gas so it's worth trying; so instead of moving base forward, we need to move it backward.

53. Maximum Subarray

Greedy is harder than DP for this problem.

Again, the key here is to make close observation, then use two-pointer strategy and increment each pointer correctly.

55. Jump Game

From each position i we have nums[i] many ways to jump, which seems to result in too many possibilities at the first glance. However, the observation is that no matter how many ways we could reach position i, what we can reach from this position onwards is the same.

Therefore, multiple jump capacities provided at different positions will always flatten to one single jump capacity. In other words, each following position will always overwrite the current jump capacity, so we only need to keep track of how far we can jump at each position, starting from i = 0

Another way of thinking is to start from the back and travel backwards, we look for the first position x that can jump to the last element (i.e. nums[x] >= distance from x to the last element), then update this position as our destination (since if we could reach x, we could reach the last element), look for position that can reach x, so on and so forth until we travel back to the first element.

Dynamic Programming

Find out the sub-problems: dp[i] (sometimes it could be multi-dimensional)
Find out the next-step-logic: dp[i + 1] = ?
Find out the base cases to start with: dp[0], dp[1], etc

1049. Last Stone Weight II

-- Use mathmatical model to simplifiy the problem

At first, the problem of recursively pairing the stones and getting resultant stones to pair again seems complicated, but after putting it into an equation everything gets very clear:

say the array is [a,b,c,d,e]
say we smash them this way result = (a-b)-c-(d-e)
rearrange the equation we get result = (a+e)-(b+c+d)

Therefore, the observation is that ultimately we just want to find a subset of the array such that sum(subset_array) is closest to sum(original_array) / 2

The power of mathmatical modelling can be seen in other problems such as: