Leetcode 518. Coin Change II

Posted on by NY Comdori

In this post, solution to leetcode problem – 518, coin change II – is explained. Please refer to this link for detail problem description.

This is very similar to combination sum IV problem. The only difference is that the order doesn’t matter and this is essentially a subset problem with duplicates. Let’s see how we can approach the problem.

Brute Force

Exhaustively enumerate all subsets and check if it makes the amount. This will have exponential cost.

Optimized version

We can follow the similar approach as combination sum IV problem. The only difference is that order doesn’t matter and if you blindly add results from previous coins, you will end up counting the duplicate as you see in the diagram below.

In the above diagram, the recurrence relation is simply adding the results from previous amount with all the coin denominations. How can we avoid counting the duplicate? Instead of looking at all the coins for each amount, we can control how many coins each node has. For example, each node is responsible for keeping track of the number of coins for only one coin. Let’s look at the diagram below.

Now, it is not counting the duplicate and you just need to add up all the nodes with valid combinations to get the final result. The recurrence relation would be f(i, a) = sum(f(i-1, a – c*coins[i])) where i is coin index, a is amount, c is number of coins. The range for c is 0 to max coins. How do you calculate max coin? It is simply amount / coins[i]. As there are overlapping subproblems, we can use dynamic programming to solve this. For this, as there are two variables, we would need two dimensional array. row represents coin index and col represents amount. (you can change row/col if you want). What’s the base case? For the first column, when amount = 0, there is only one combination to make the amount – empty subset. For the first row, when no coins are used – I remember I said row is coin index, but since index makes problem slightly more difficult, let’s say row is ith coin that 0th coin means no coin, and the first coin is the first coin in coins – there isn’t any combination possible to make any amount. So everything is 0 except the first column. Although there are more optimizations possible, let’s take a look at the pseudo-code

table: 2d array of row (num coins + 1) col (amount + 1)
initialze first column to 1. everything else is 0

for i in 1 to n: // n is number of coins
    for a in 1 to amount:
        maxCoins = a / coins[i-1]  // note that i is index of table. to access corresponding coin, need to subtract 1
        // check all the possible number of coins can be included
        for c in 0 to maxCoins:
            table[i][a] += table[i-1][a - c*coins[i-1]]
            
return table[n][amount]

Solution is very simple but look at the time complexity. We already have a 2D table and there is an additional for-loop for each cell in the table. Can we do better?

More optimized version

If you closely look at the code, we can eliminate the inner for-loop (c) while achieving the goal. Instead of checking possible number of coins in the for-loop, let’s look at from exclusion/inclusion point of view. At each amount and coin[i], we have a choice – exclude or include. If you exclude, then you check the next coin. If you include, you have another choice – exclude or include the same coin again.

With that, we have a better time complexity. Here is the code written in C++.

int change(int amount, vector<int>& coins) {
    vector<vector<int>> table(coins.size()+1, vector<int>(amount+1, 0));
    for (int i = 0; i <= coins.size(); ++i)
    {
        table[i][0] = 1;
    }

    for (int i = 1; i <= coins.size(); ++i)
    {
        for (int j = 1; j <= amount; ++j)
        {
            // exclude
            table[i][j] = table[i-1][j];

            // include
            if (j >= coins[i-1])
            {
                table[i][j] += table[i][j-coins[i-1]];    
            }
        }
    }
    
    return table[coins.size()][amount];
}

Time complexity=O(n*amount) where n is length of coins and amount is initial amount. Space complexity=(n*amount) because we create 2D array of n*amount. We are very close but there is one more optimization we can achieve – space complexity. If you look at the all the update, exclude code at line 13 is completely unnecessary because after processing the row, next row can start exactly same as previous row. In addition to that, when you look at inclusion code at line 18, you only look at previous column because you are including the same coin!

It means that we only need a 1D array. Here is the C++ code.

int change(int amount, vector<int>& coins) {
    vector<int> table(amount+1, 0);
    table[0] = 1;

    for (int i = 1; i <= coins.size(); ++i)
    {
        for (int j = 1; j <= amount; ++j)
        {
            if (j >= coins[i-1])
            {
                table[j] += table[j-coins[i-1]];
            }
        }
    }
    
    return table[amount];
}

Time complexity is unchanged because you have to iterate all the coins with all the amount. However, we reduced the space complexity to O(amount).

Leetcode 377. Combination Sum IV

Posted on by NY Comdori

This post explains how to solve leetcode 377. combination sum IV problem. It starts with brute force idea and optimize to efficiently solve the problem. Please refer to this link for problem detail.

In this problem, you have two arguments – target and nums array. You are supposed to find the number of combinations to make the target amount only using numbers in nums array. In this problem, the order matters as you see in the example.

Let’s think about brute force idea – enumerate all the possible subsets of nums array. For each subset, you also need to check how many of each number can make the target. This is very expensive with exponential time complexity.

Can we do better? Let’s suppose nums = [1,2,3] and target is 10. Now, let’s also suppose that we have collected a number of combinations right before 10. In other words, we have the result at 9, 8, 7 which are (10 – 1), (10 – 2), (10 – 3). Since the order matters, we need to count all three cases. Then, the answer would be result(10 – 1) + result(10 – 2) + result(10 – 3). We can recursively derive the same relationship for 9, 8, 7 values. Let’s take a look at the below diagram.

We just need to recursively look for children until the base case is reached, which is 0. This is better than enumerating all the subsets and finding combinations. However, there is still room to improve because there are overlapping subproblems. This overlapping subproblem is like calculating fibonacci number recursively. We prevent calculating the same subproblem by storing the result. If subproblem is found, then we just need to reuse that one. Ultimately this becomes dynamic programming.

There are two ways – bottom up, top down – to solve the problem. In this post, I will just explain bottom up approach.

Let’s define f(t) as “number of combinations based on number in nums at target amount t”

Subsequently, the recurrence relation would be f(t) = sum(f(t – nums[i])), where i is 0..nums.length() (index). If t – nums[i] < 0, then it would be 0 as you can’t have negative value.

With the recurrence relation clearly defined, the code becomes very simple. The solution is based on C++.

Base case is t=0. There is only 1 way to make amount 0 which is empty subset. Based on the base case, we need to build up from the bottom until reach the target amount.

int combinationSum4(vector<int>& nums, int target) {
    vector<unsigned int> table(target+1);
    table[0] = 1;
    for (int i = 0; i <= target; ++i)
    {
        for (int num : nums)
        {
            if (i >= num)
            {
                table[i] += table[i-num];
            }
        }
    }

    return table[target];
}

The time complexity is O(nt) where n is length of nums and t is target amount. One gotcha is that if t is really large (ex. > 2^n) this essentially becomes same as brute force solution.

Maximum Repeating Substring

Posted on by NY Comdori

This is an easy level coding interview problem from leetcode. The problem asks you to find the maximum number of repeating string which is given. Please refer to the problem description for more detail. For the solution, you need to iterate the sequence. At each index, you check if the substring matches the word. If it matches, then continue to the next index to find the end of the repeated word. If it doesn’t match, then just move on to the next index.

I provided solutions in C++ and Python3. You can try iterative solution but I provided recursive solutions here. For recursive solutions, it is following the same principles. But note that I keep track of the start index of the comparison because that will be used when the substring doesn’t match. 

void maxRepeating(const string &seq, int currIdx, int matchIdx, const string &word, int numRepeat, int &maxRepeat)
{
    // this is base case. make sure you get the max repeat.
    if (seq.size() - matchIdx < word.size())
    {
        maxRepeat = max(maxRepeat, numRepeat);
    }
    // word doesn't match. get the max repeat and then continue comparing the string from the currIdx which is the start of the matching
    else if (seq.substr(matchIdx, word.size()) != word)
    {
        maxRepeat = max(maxRepeat, numRepeat);
        maxRepeating(seq, currIdx + 1, currIdx + 1, word, 0, maxRepeat);
    }
    // word matches. keep checking. make sure currIdx is passed to note the start of the pattern
    else
    {
        maxRepeating(seq, currIdx, matchIdx + word.size(), word, numRepeat + 1, maxRepeat);
    }
}

int maxRepeating(string sequence, string word) {
    int maxRepeat = 0;
    maxRepeating(sequence, 0, 0, word, 0, maxRepeat);
    return maxRepeat;
}
class Solution:
    result = 0
    
    def max_repeating(self, sequence, curr_idx, match_idx, word, num_repeat):
        compare = sequence[match_idx : match_idx + len(word)]
        if len(compare) < len(word):
            self.result = max(self.result, num_repeat)
            return
        elif compare != word:
            self.result = max(self.result, num_repeat)
            self.max_repeating(sequence, curr_idx + 1, curr_idx + 1, word, 0)
            return 
        
        self.max_repeating(sequence, curr_idx, match_idx + len(word), word, num_repeat + 1)
        
    
    def maxRepeating(self, sequence: str, word: str) -> int:
        self.max_repeating(sequence, 0, 0, word, 0)
        return self.result

Longer Contiguous Segments of Ones than Zeros

Posted on by NY Comdori

This is an easy level leetcode problem. Please refer to this link for the detail of the problem description.

Basically, the idea is to find the longest consecutive 1’s and 0’s and return True if 1’s > 0’s.

There are a couple of ways to achieve the problem.

The first one is a pythonic way. Since the string is a binary string that only has 1 and 0, you can split the string based on them. After the split, it’s really to find the longest string in the array. But this solution is only applicable to python.

class Solution:
    def checkZeroOnes(self, s: str) -> bool:
        return max((len(digit) for digit in s.split('0'))) > max((len(digit) for digit in s.split('1')))

Another solution is to explicitly iterate the string and count num 1’s and 0’s which are applicable to all other languages. You can do it in one pass as you see the solution below.

class Solution:
    def checkZeroOnes(self, s: str) -> bool:
        ones_start_idx = 0
        num_ones = 0
        zeros_start_idx = 0
        num_zeros = 0
        for idx, digit in enumerate(s):
            if digit == '0':
                ones_start_idx = idx + 1
                num_zeros = max(num_zeros, idx - zeros_start_idx + 1)    
            else:
                zeros_start_idx = idx + 1
                num_ones = max(num_ones, idx - ones_start_idx + 1)
            
            
        return num_ones > num_zeros

Delete Characters to Make Fancy String

Posted on by NY Comdori

This is an easy level leetcode problem, which you can use stack to solve.

Please refer to this link for more detail of the problem.

Essentially, you cannot accept 3 or more consecutive duplicate letters. There could be many ways but using a stack seems to be the most elegant approach. Basically, you accumulate each letter if it doesn’t match with the top two entries in the stack or stack has less than 2 elements. This way, you are only accumulating letters that are not duplicate of 3 or more consecutive characters.

class Solution:
    def makeFancyString(self, s: str) -> str:
        fancy = []
        for letter in s:
            if len(fancy) < 2 or fancy[-1] != letter or fancy[-2] != letter:
                fancy.append(letter)
            
        return "".join(fancy)

Check Whether Two Strings are Almost Equivalent

Posted on by NY Comdori

This is a leetcode interview problem that requires a hash table with strings. Please refer to this link for more detail of the problem description.

Let me first show you the solution code.

class Solution:
    def checkAlmostEquivalent(self, word1: str, word2: str) -> bool:
        def default_val():
            return list((0, 0))
        count = defaultdict(default_val)
        for letter in word1:
            count[letter][0] += 1
        
        for letter in word2:
            count[letter][1] += 1
            
        for letter, freq in count.items():
            if abs(freq[0] - freq[1]) > 3:
                return False
            
        return True

A hash table is necessary in order to keep track of the frequencies of the letter in the word. Note that I used a list of which size is 2 – the first index is frequencies for word1 and the second index is frequencies for word2.

Once you collected the frequencies, you just need to check if the frequency difference is greater than 3.

Golang – labeled break and continue

Posted on by NY Comdori

break and continue are keywords that control the loop in many programming languages. The scope of those keywords is at inner most. Here is the example code of C++.

for (int i = 0; i < 5; ++i) {
    for (int j = 0; j < 5; ++j) {
        if (i == 1 && j == 3) {
            break;
            // continue;
        }
    }
}

In the example code above, break and continue will only affect the inner most loop which deals with the variable j. However, in golang, you can control the scope of break and continue keyword by using labels.

Here is the example code.

package main

import (
	"fmt"
	"os"
	"strings"
)

func main() {
	library := `
	I am learning computer science and computer engineering
	`
	words := strings.Fields(library)
	query := os.Args[1:]

queries:
	for _, q := range query {
		for i, w := range words {
			if q == w {
				fmt.Printf("index %d: %q\n", i, w)
				break queries
			}
		}
	}
}

Let’s say there is a library of words and you are querying unique words. For example, when you query the word computer, it should return the first index of the word and the word itself. As you are running the loop, there are multiple ways to achieve this. But I want to show you that you can use a label to control the scope. You can declare the label at any scope you want and use the label with break or continue keyword. As you see in the above code, it will exit the entire thing once it finds the word.

go run main.go computer
index 3: "computer"

Go Lang – Printf Cheat Sheet

Posted on by NY Comdori

This is a go lang Printf cheat sheet post. Essentially it is very similar to the one in C. Just like the one in C, Printf really prints the string in a formatted way. It is very convenient to have a cheat sheet since I always forget unless I use it frequently. This mainly focuses on examples.

print type of variable %T

var intNum int
var floatNum float64
var boolVal bool
var strVal string

fmt.Printf("%T\n", intNum)
fmt.Printf("%T\n", floatNum)
fmt.Printf("%T\n", boolVal)
fmt.Printf("%T\n", strVal)

// output
int
float64
bool
string

print int type %d

This prints integer type. It will perform type check and will give you a warning that type doesn’t match. And of course the result format will be odd.

age := 21
fmt.Printf("age: %d\n", age)
fmt.Printf("age: %s\n", age)

// output
age: 21
age: %!s(int=21)

print float %f

%f prints floating numbers. Since this is a floating number, you can control the precision with “.<number>”
Increasing precision means the floating number will be more precise.

floatNum := 224.701
fmt.Printf("num: %f\n", floatNum)
fmt.Printf("num: %.0f\n", floatNum)
fmt.Printf("num: %.1f\n", floatNum)
fmt.Printf("num: %.2f\n", floatNum)
fmt.Printf("num: %.3f\n", floatNum)
fmt.Printf("num: %.4f\n", floatNum)
fmt.Printf("num: %.5f\n", floatNum)

// output
num: 224.701000
num: 225
num: 224.7
num: 224.70
num: 224.701
num: 224.7010
num: 224.70100

print bool %t

male := true
female := false

fmt.Printf("are you male?: %t\n", male)
fmt.Printf("are you femail?: %t\n", female)

//output
are you male?: true
are you femail?: false

print string type %s, %q

Those print the strings. However, there is a difference between them. %s just prints the string itself but %q prints with double quotes.
Note that \n is just an escape sequence providing a new line. This also performs type checks.

name := "Google"
fmt.Printf("%s\n", name)
fmt.Printf("%q\n", name)

// output
Google
"Google"

print any value %v

This prints all the provided values. It’s very convenient but it doesn’t guarantee any type safety. For example, what if you only want to print int instead of string or float? %v will not check anything and print as-is.

name := "Google"
val := 1
floatVal := 1.123
fmt.Printf("%v %v %v\n", name, val, floatVal)

// output
Google 1 1.123

Argument Index

Typically you have to provide a value for each verb in the Printf format string. However, there is an exception to this rule. You can refer to the already provided variable. This is called argument index. Note that [1] refers to the first argument which is “name”. [2] refers to the second argument. Why does the index start from 1? It’s because index 0 of the Printf is the format string.

name := "NY Comdori"
job := "software engineer"

fmt.Printf("%v is a %v. Being %[2]v is fun! Good luck %[1]v!\n", name, job)

// output
NY Comdori is a software engineer. Being software engineer is fun! Good luck NY Comdori!

Go lang – iota and constants

Posted on by NY Comdori

In programming languages such as C++ and Java, there is Enum type which is used frequently. In go language, you can use iota to represent an Enum type.

Let’s take a look at a simple example

Example

Let’s say you want to define variables to represent weekdays. In that case, you probably just want to have integer values for a simple comparison. (You really don’t want to use string to represent the value unless you are printing) Let’s take a look at a version that naively represents the weekdays.

const (
	SUNDAY = 0
	MONDAY = 1
	TUESDAY = 2
	WEDNESDAY = 3
	THURSDAY = 4
	FRIDAY = 5
	SATURDAY = 6
)

// output
fmt.Println(SUNDAY, MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY)

0 1 2 3 4 5 6

Now it will perfectly fine because you can use those variables like others. However, it is very tedious to explicitly type all the values because you really don’t care about those. You just want consecutive integers. Here is where iota comes into play to make life better.

What is iota? It is a built-in constant generator that generates consecutively increasing numbers. Let’s take a look at the usage

const (
	SUNDAY = iota
	MONDAY
	TUESDAY
	WEDNESDAY
	THURSDAY
	FRIDAY
	SATURDAY
)

// output
fmt.Println(SUNDAY, MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY)

0 1 2 3 4 5 6

With iota, you only need to assign iota once to the place you want to generate. iota always starts from 0 and will increase the number and repeat the same assignment as the previous line. In the example above, SUNDAY will be 0. For MONDAY, iota will repeat itself with the increased number which is 1. It will stop once it reaches the end and the value will be reset to 0 so that it won’t disrupt other constant settings. What happens if you want to use iota from the middle part? 

const (
	SUNDAY = -1
	MONDAY = iota
	TUESDAY
	WEDNESDAY
	THURSDAY
	FRIDAY
	SATURDAY
)

// output
fmt.Println(SUNDAY, MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY)
-1 1 2 3 4 5 6

You just have to explicitly set the value before the iota usage. iota will start from there. Note that iota value starts from 1 instead of 0.
Why is that? It’s because iota starts from the beginning of the constants.

Blank Identifier

You can use a formula to set a custom value using iota. iota always starts from 0 and if you want a different value, you have to use some expression to do that. Let’s say you want to represent different timezones in constants. You only want to represent three timezones in the U.S. – EST, MST, PST – compared to UTC. For example, EST means the eastern standard time that is -5 hours behind UTC. MST means mountain time that is -7 hours behind UTC. PST means the pacific time that is -8 hours behind UTC. Therefore you want to have your constants represent like this.

const (
	EST = -5
	MST = -7
	PST = -8
)

fmt.Println(EST, MST, PST)
-5 -7 -8

But how can you use iota here? There are two issues here. iota will return a non-negative increasing number but you want to have negative numbers here. The second issue is that the values we want are not consecutive. Let’s tackle the issue one by one. How can we have negative numbers using iota? We can use a formula to manipulate the value.

const (
	EST = -(iota + 5)
	MST
	PST
)

fmt.Println(EST, MST, PST)
-5 -6 -7

You can use a typical mathematical expression when using iota because it just returns a number.

Now, there is still an issue here. We want -5, -7, -8 but actually got -5, -6, -7 because iota only returns consecutively increased numbers. What can we do? Remember that iota will always increase the value in every line. But We certainly don’t want to declare any dummy constant just for that. Blank identifier comes to the rescue. Blank identifier in go is to tell the compiler this is unused variable and ignore it. It is ‘_’. 

const (
	EST = -(iota + 5)
	_
	MST
	PST
)

fmt.Println(EST, MST, PST)
-5 -7 -8

Now, note that iota will increase by 1 at line 3. We all know that ‘_’ is a dummy and can just ignore. In MST, it will be set to -7 which is the correct value now.

Conclusion

We have briefly taken a look at iota and constants in go lang. It could be pretty convenient when used properly. Happy coding!

Intro to CSS Grid Layout Part 5

Posted on by NY Comdori

This is intro to CSS grid layout part 5. So far we have taken a look at following topics. It is recommended to take a look if you are not familiar with css grid layout basics.

In this post, I will focus on explaining how to use grid area with area names for positioning grid items with an example. Let’s take a look it.

Example

We have a layout of multiple items. Note that the header is not spanning to the end but the last slot is empty.

HTML Code

This is the html code used for the example

<div class="challenge">
  <div class="header">Header</div>
  <div class="small-box-1">Small box</div>
  <div class="small-box-2">Small box</div>
  <div class="small-box-3">Small box</div>
  <div class="main-content">Main content</div>
  <div class="sidebar">Sidebar</div>
  <div class="footer">Footer</div>
</div>


CSS Code

We have 4 rows and 4 columns which make 16 unit areas. To use area based positioning, you need to define each unit area with an area name. You can decide the name as you prefer. As you can see, grid-template-areas property is defined with 16 names. For example, head is located at the first row and spanning from first to third column. “.” represents an empty slot. After you define the area representation, all you need to do is to specify the area name for each class. Take a look at line 21 and others.

.challenge {
  width: 1000px;
  margin: 30px auto;
  
  display: grid;
  grid-template-rows: 100px 200px 400px 100px;
  grid-template-columns: repeat(3, 1fr) 200px;
  grid-gap: 35px;
  grid-template-areas: "head head head ."
                      "small-box-1 small-box-2 small-box-3 side"
                      "main main main side"
                      "foot foot foot foot";
  
  & > * {
    background-color: orangered;
    padding: 15px;
    color: white;
    font-size: 30px;
    font-family: sans-serif;
  }
  .header {
    grid-area: head;
  }
  
  .small-box-1 { grid-area: small-box-1; }
  .small-box-2 { grid-area: small-box-2; }
  .small-box-3 { grid-area: small-box-3; }
  
  .sidebar {
    grid-area: side;
  }
  
  .main-content {
    grid-area: main;
  }
  
  .footer {
    grid-area: foot;
  }
}

It is very important to note that you have to have a complete area representation. Since you have 16 unit slots (4 rows * 4 columns), you have to have 16 area names in order to use it. It is fairly simple to use for a simple area layout. However, if you have a complex layout, it could be inconvenient to use it. i.e., 10 rows and 10 columns. In such a case, it would be better to use grid lines instead of names.