Contains my answers to problems solved on variouse competitive programming sites
Using Clang in Visual Studio Code
bits/stdc++ is a GNU GCC extension, whereas OSX uses the clang compiler. So we will not have access to this header. In order to add this header we have to first find out where to put it.
run:
echo "" | gcc -xc - -v -E
This will give you a large sum of output but what we want is to find where it uses the #include
look for the one with include at the end.
Once we have this lets go into that directory and make a new directory called bits
cd /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include
sudo mkdir bits
now go into bits and add stdc++.h
run the following command in the same directory as the stdc++.h file. Note that the path you are copying should match the 'include' path you retrieved earlier.
sudo cp stdc++.h /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/bits/stdc++.h
note there where a few issues with the __cplusplus preprocessor macro so a had to move a few of the libraries around but once I did that it seemed to be working fine.
We use C++ 17 because LeetCode does not support C++ 20
Always suss out your constraints. Example graph question constraints:
n == rooms.length2 <= n <= 1000the array length is between 2 and 10000 <= rooms[i].length <= 1000the adjacency list values have an array length between 0 and 10001 <= sum(rooms[i].length) <= 30000 <= rooms[i][j] < nthe value in the adjacency list is always less than nAll the values of rooms[i] are unique.each value in the adjacency list for the node is unique
A lot of parsing questions (valid parentheses, braces, parsing math expressions), and basically anything where 'future data can impact earlier'. Another pattern would be monotonically increasing / decreasing stack questions, where you eliminate all entries greater / less than on each iteration.
Two common use cases:
- Finding an optimal solution ie: max or min
- Counting the total number of solutions for a problem
examples may include:
- What is the minimum cost of doing...
- What is the maximum profit from...
- How many ways are there to do...
- What is the longest possible...
- Is it possible to reach a certain point...
2D vs 1D Identifying a 2D dynamic programming problem can be tricky but with DP especially top down it is all about memoization. If I have a question where im trying to see if I can make 'X' give items 'Y' and I can reuse items 'Y' as many times as I like then why bother keeping track of 'Y' because 'Y' is not important in this case because I can just reuse it as much as I like because in the end all I care about is if I can make 'X' from 'Y'. This is a good example of 1D because no need to keep track of Y's state.
If on the other hand I can not reuse 'Y' and I can only use these items once well now I need a way to keep track of what I have/havn't used. In this case I need to keep track of Y's state. This is a good case for a 2D dynamic programming question.
So in the end ask yourself "do i need to keep track of theses items state?", if not then 1D otherwise 2D. The state you need to track determines the dimension of the array.
Dynamic Programming can be performed in bottom-up (iterative) approach or top-down (recursive with memoization). If not sure how to perform memoization for top-down think about memoizing the function call which in our case would be the arguments provided to the function at that time of calling it. A good example of how I did this here 1770. Maximum Score from Performing Multiplication Operations
Sometimes (i say sometimes because that may not always be the case) it can be easier to to do the top-down approach first and then translate this over to bottom-up for improved performance. A good example of this is:
- 1143 Longest Common Subsequence
- 188 Best Time to Buy and Sell Stock IV
- 714 Best Time to Buy and Sell Stock with Transaction Fee
cases where it was easier to perform bottom-up vs top-down:
Note: state reductions for space complexity usually only apply to bottom-up implementations, while improving time complexity by reducing the number of state variables applies to both implementations.
Another common scenario for improving space complexity is when the recurence relation is static (no iteration) along one dimension (flat array). An example of this is nth fibonacci number. Because we only care about the previouse 2 fibonacci numbers there is no need to keep an array holding all previouse fibonacci numbers.
Kadane's Algorithm is an algorith that can find the maximum sum subarray when given an array of numbers. Its time complexity is O(n) and space O(1).
// Given an input array of numbers "nums",
1. best = nums[0]
2. current = nums[0]
3. for num in nums[1:]: // start at index 1
3.1. current = Max(current + num, num)
3.2. best = Max(best, current)
4. return best
- Good for finding the top K elements.
- Dijkstras algorithm for calculating the shortest path in weighted graphs.
- The condition for using the sliding window technique is the problem asks to find the
max/minvalue for a function that calculates the answer repeatedly for a set ofrangesfrom the array. Example Leetcode 1004: Given a binary array nums and an integer k, return the maximum number ofconsecutive 1's(consecutive 1's creates a range) in the array if you can flip at most k 0's.
- Great for finding the shortest path in the graph.
- Can be used with priority queue to form Dijkstras algorithm to find shortest path in weighted graph
Although binary search algorithms are typically used to find one element in a sorted sequence, they have many other uses. You can apply a binary search to a result, for example. Say you wanted to determine the minimum square footage of office space needed to fit all a company's employees easily. The square footage is a consecutive number and therefore sorted so we can perform binary search on it
Used for finding the start of a linked list cycle.
Used to find the greatest common divisor between two numbers
func gcd(a, b int) int {
if b == 0 {
return a
}
return gcd(b, a%b)
}Used to find the articulation point in a graph. An articulation point is a node that when removed will divide the graph into 2.
- LeetCode Hard - 1568 minimum number of days to disconnect island.
- YouTube: Tarjan's Strongly Connected Component (SCC) Algorithm (UPDATED) | Graph Theory
Sometimes you might have an array that cycles back arround.
For example this will always find the indexes 2 infront of the current index when the array is a loop.
(i + 1) % len(array) , (i + 2) % len(array)
i, arrLen := 1, 3
(i + 1) % arrLen = 2
(i + 2) % arrLen = 0 // looped back around
- 256 Paint House
- 265 Paint House II arrLen varies per input
Find the sum all numbers up to n in O(1) time. For example if I said find the sum of the first 100 numbers you could loop through all the numbers from [1..n] to get the sum which would take O(n) time or you could use the below formula:
n := 100
sum := n * (n+1) / 2
Will produce a bit in the same position where x and y have the same bit.
1 0 1 1 0 (22)
& 1 1 0 1 0 (26)
----------------
1 0 0 1 0 (18)
Because in Binary even numbers always have their right most bit as 0 we can quickly determine if a number is even by:
x & 1 == 0
and converseley if its odd by (because odd numbers always have their right most bit as 1):
x & 1 == 1
Will produce a bit in the same position where one of the bits is 1.
1 0 1 1 0 (22)
& 1 1 0 1 0 (26)
----------------
1 1 1 1 0 (30)
Will produce a bit in the same position where both bits are different.
1 0 1 1 0 (22)
& 1 1 0 1 0 (26)
----------------
0 1 1 0 0 (12)
An example of this can be found here LeetCode 268 Missing Number
Used to invert the bits. The formula ~x == -x - 1 holds true. In Go there is no ~ operator but we can use XOR.
^29 = -30
This holds true to ~x == -x - 1
Left bit shift << appends K zero bits to the number and Right bit shift >> removes K zero bits from the number. NOTE:
x << k is the same as x * 2^k
x >> k is the same as x / 2^k
Some questions becasue the number can get really large ask you to mod by 1,000,000,007. This is equivalent to 1e9+7. 1e9 is the same as saying 1 multiplied by 10^9. Therefore we can do the following:
answer % (1e9+7)
