Documentation
¶
Index ¶
- func BuyAndSell(price ...int) (profits int)
- func MaximumOfAnySubarray(input ...int) int
- func MaximumProductSubarray(input []int) int
- func MinimumOfRotatedSortedArray(input []int) int
- func MissingNumber(input ...int) (output int)
- func RemoveDuplicates[T cmp.Ordered](sorted []T) []T
- func RotateR[T any](list []T, k int)
- func SearchInRotatedSortedArray(input []int, target int) int
- func SetMatrixZeros(input [][]int)
- func ThreeSum(data []int, target int) (result [][]int)
- func TwoSum(input []int, target int) []int
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func BuyAndSell ¶
BuyAndSell produces the maximum possible sum from any subarray of the input.
From LeetCode: "You are given an array prices where prices[i] is the price of a given stock on the ith day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0."
This question modifies MaximumOfAnySubarray by requiring both a "buy" and a "sell" price. In other words, the input needs to contain at least two values. Moreover, because the question asks about profit, the result must be positive.
Let's write this first relying on the earlier implementation, adding just these additional constraints, then rewrite the entire function to be more concise. Here's where we would start
func BuyAndSell(price ...int) (profit int){
if len(price) < 2 {
return
}
profit = MaximumOfAnySubarray(price...)
if profit < 0 {
return 0
}
return profit
}
CRLS Chapter 4, Section 1 gives the necessary hint: "instead of looking at the daily prices, let us instead consider the daily change in price..."
Yet the problem with this chapter is that the authors discuss a universal generalization that's valid for *all* recurrence relations under the formal constraint
T(n) = aT(n/b) + f(n)
We do not need that level of generality in this problem.
func MaximumOfAnySubarray ¶
MaximumOfAnySubarray produces the maximum possible sum from any subarray of the input.
From LeetCode: "Given an integer array, find a subarray with the largest sum, and return its sum. Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle."
CRLS Chapter 4, Section 1 describes solutions to this problem, initially framed as a solution to BuyAndSell. But the Claude produced solution gives another way with Kadane's Algorithm, which can be described as a "divide and conquer" solution yet reads much more simply in practice.
Note that this will be zero by default, when the original input is empty. When the input has just one integer, the maximum is that integer. In all other cases, we need to keep track of the current subarray summation and the overall maximum.
We'll accomplish this by setting both the current and the maximum to the first integer as a base case. Then we loop over all remaining integers, starting at the second index. The for loop construct prevents us from overrunning the input.
On each iteration, add the ith integer to the current value. Replace the current value with the larger of the sum or the input value. Then, replace the maximum if the current is greater. Continue.
Once the loop terminates - as it ought to given the boundary constraint `i < len(input)`, we have an answer to the prompt.
func MaximumProductSubarray ¶
MaximumProductSubarray
From LeetCode Problem 152: "Given an integer array nums, find a subarray that has the largest product, and return the product. The test cases are generated so that the answer will fit in a 32-bit integer."
This problem modifies MaximumOfAnySubarray. We could swap the addition for multiplication
```go
func MaximumProductSubarray(input ...int) (maximum int) {
if len(input) == 0 {
return
}
current := input[0]
maximum = current
for i := 1; i < len(input); i++ {
current = max(input[i], current * input[i])
maximum = max(current, maximum)
}
return
}
```
but this returns the maximum overall product from the array, not a subarray. In order to tell the difference, we need to determine if and when the accumulated product switches sign from `p > 0` to `p <= 0`.
Thinking about this algorithmically, we have two comparison points when all inputs are positive and non-zero. We must need then two more comparison points when some inputs are zero or less, giving us four overall
- current maximum - current minimum - maximum - minimum
The current maximum and current minimum will be compared with each other and the input value to update teh maximum and minimum. Then the overall maximum will be updated from just the maximum as before
func MinimumOfRotatedSortedArray ¶
MinimumOfRotatedSortedArray
From LeetCode problem 153: "Suppose an array of length n sorted in ascending order is rotated between 1 and n times. Given the sorted rotated array nums of unique elements, return the minimum element of this array. You must write an algorithm that runs in O(log n) time."
First hint here comes in that the input already comes sorted monotonically before rotation. After rotation, then, the smallest item must come after the largest. We could step through from the beginning to see when A > B, giving B as the answer. However, this would be an O(n) runtime.
For an O(log n) time, cut the slice down the middle. If the last element of the left is larger than the last element of the right, recurse on the left, otherwise, recurse on the right. Why? Again, we're relying on the fact that the data initially come sorted, so, if L < R the minimum must be somewhere in L.
```go
func MinimumOfRotatedSortedArray(input []int) int {
if len(input) == 1 {
return input[0]
}
l, r := input[:len(input)/2], input[len(input)/2:]
a, b := l[len(l)-1], r[len(r)-1]
if a < b {
return MinimumOfRotatedSortedArray(l)
}
return MinimumOfRotatedSortedArray(r)
}
```
Claude gives a solution with just three local variables for indices and is technically more space efficient. My solution uses more memory because I'm copying the left and right halves of the input slice, and doing so recursively.
Here's what Claude gives verbatim ¶
```go
func findMin(nums []int) int {
left, right := 0, len(nums)-1
for left < right {
mid := left + (right-left)/2
if nums[mid] > nums[right] {
left = mid + 1
} else {
right = mid
}
}
return nums[left]
}
```
I like my solution better, and the runtime memory difference isn't terrible (something like 0.2MB more) but unfortunately neither solution make the necessary refactor for SearchInRotatedSortedArray clear to me. So I refactored the Claude solution into a switch statement in anticipation of those modifications.
func MissingNumber ¶
MissingNumber
From LeetCode: "Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array. Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?"
The sum of all numbers from 0 to N is expressed by the sum of an arithmetic series, usually attributed to Gauss
S = N * (N + 1) / 2
Since, according to the problem, exactly one number is missing from the input, subtract each input number from the expected summation.
Claude gives an interesting alternate solution that uses an XOR to find the missing number ¶
```
func missingNumber(nums []int) int {
missing := len(nums)
for i, num := range nums {
missing ^= i ^ num
}
return missing
}
```
The only advantage here is that we do not need to compute the summation. This works because every number in input gets XOR'd twice except for the missing number, leaving its bits in the missing value. But it's harder for a human to read and understand. We'd really need to inspect the machine code to decide if the assembly instructions make enough of a difference. If we're doing that, then it's unlikely the real-world problem would be stated as cleanly as the LeetCode problem.
func RemoveDuplicates ¶
RemoveDuplicates
From LeetCode problem 80: "Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same."
Note that whenever the input slice is 2 or fewer items, we have met the necessary conditions and may return immediately. Otherwise, we need to use two indices, one fast and one slow. The funny part here is how the indices start at the same position.
Our comparison happens at `slow-2` and `fast` because the progression of the slow index ought to tell us where we want to keep data. If the data are the same during the comparison, we ought to move the fast index ahead. Otherwise, we can move the data back towards the front of the slice. Once done, the slow index shows us where we want to truncate for the return value
func RotateR ¶
RotateR
From LeetCode problem 189: "Given an integer array nums, rotate the array to the right by k steps, where k is non-negative."
The Go builtin `copy` and `append` functions give us a freebie here. By using just these two functions, we can have a time and space optimal solution.
First, notice we're moving rightwards. If we do this in a loop, for each k iterations, we prepend the last item to the beginning of the slice, shifting everything over by one.
Yet we can do this all at once if we cut the slice at k then swap the left and the right. In case the value k is larger than the length of the slice, we calculate `k = k % len(list)` to get a smaller cut point. We then find `len(list) - k` to indicate the cut point, and use append to paste the two pieces back together. Finally, `copy` assures we move all the slice data back into the original memory location.
We allow the compiler to do the hard work for us ;)
func SearchInRotatedSortedArray ¶
SearchInRotatedSortedArray
From LeetCode problem 33: "There is an integer array nums sorted in ascending order (with distinct values). Prior to being passed to your function, nums is possibly rotated at an unknown pivot index. For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2]. Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums. You must write an algorithm with O(log n) runtime complexity."
In this problem, we're again performing a binary search, but with the caveat that we want to return the index for a match. This match *will not* be a minimum in general. We start with the original and note that there's three match possibilities in general:
- the value at index i matches the target - the value at index j matches the target - the value at index k matches the target
We'll simply add these to the switch statement as cases. Next, we need to consider when to move left or right to continue searching. There's exactly four possibilities here:
1. the left hand side remains sorted and contains the target 2. the left hand side remains sorted but does not contain the target 3. the right hand side contains the target 4. the right hand side does not contain the target
Possibilities (1) and (4) mean we search left, whereas (2) and (3) mean we search right.
It actually takes quite a bit of analysis to reduce to these 4 cases. Claude gives a correct solution using nested if statements that's difficult to understand. The LLM copied the solution from examples from its training data, but I want to do better here, so I put in the work to analyze and describe it.
Note something important: cases (3) and (4) don't explicitly say whether the right hand side must be sorted. Why? Well, if the left remains sorted then necessarily so does the right, therefore by case (2) we no longer need that information. Case (3) therefore, only asks what cases (1) and (2) cannot, and (4) presents the default by symmetry.
func SetMatrixZeros ¶
func SetMatrixZeros(input [][]int)
SetMatrixZeros
From LeetCode: "Given an m x n integer matrix, if an element is 0, set its entire row and column to 0's. You must do it in place."
To solve this problem, we need to preform at least two loops over the entire input matrix. First, we need to find the rows and cols that contain a zero. Then, we need to use what we found to write over the values in those columns.
```go
func SetMatrixZeros(input [][]int) {
rows := map[int]struct{}{}
cols := map[int]struct{}{}
for i := range input {
for j := range input[i] {
if input[i][j] == 0 {
rows[i] = struct{}{}
cols[j] = struct{}{}
}
}
}
for i := range input {
for j := range input[i] {
if _, zero := rows[i]; zero {
input[i][j] = 0
continue
}
if _, zero := cols[i]; zero {
input[i][j] = 0
continue
}
}
}
}
```
This solves the problem in a straightforward and easy to understand fashion. We only need to know the matrix access pattern: a nested loop.
The follow-up on the question suggests we might give a constant space solution. What we have now takes O(m + n) space, that is, up to `m := len(rows)` and `n := len(cols)` where every cell in the matrix m-by-n contains zeros.
The trick, revealed by Claude's solution, repurposes the first row and first column of the input matrix to use to keep track of the zeros in the (m-1) by (n-1) submatrix. In the first loop, zero out the corresponding first row and first column if the item i,j is zero
```go
for i := range input {
for j := range input[i] {
if input[i][j] == 0 {
input[i][0] = 0
input[0][j] = 0
}
}
}
```
then in the second loop, we can check the first row and first column to decide to zero out the item
```go
for i := range input {
for j := range input[0] {
if input[i][0] == 0 || input[0][j] == 0 {
input[i][j] = 0
}
}
}
```
This works perfectly for zeroes in the submatrix, but there's two scenarios we might miss. Consider the matrix
0 1 2 0 0 0 0 0
3 4 5 2 -> 0 4 5 0
1 3 1 5 0 3 1 0
as written, the first pass through the second loop will write
0 0 0 0
3 4 5 2
1 3 1 5
this has the side effect where the second pass will clear the second row based on the first, and the third pass will clear the third row based on the second.
```go
func SetMatrixZeros(input [][]int) {
for i := 1; i < len(input); i++ {
for j := 1; j < len(input[i]); j++ {
if input[i][j] == 0 {
input[i][0] = 0
input[0][j] = 0
}
}
}
for i := 1; i < len(input); i++ {
for j := 1; j < len(input[i]); j++ {
if input[i][0] == 0 || input[0][j] == 0 {
input[i][j] = 0
}
}
}
}
```
which clears the third column but not the first row or first column
0 1 2 0 0 1 2 0
3 4 5 2 -> 3 4 5 0
1 3 1 5 1 3 1 0
Hence, we need to separately track those initial values. Given there's one of each, we'll use a boolean flag, then clear out each if the flag's set. This gives the final, correct version below.
func TwoSum ¶
TwoSum produces the indices from an array where the sum of the values matches a target.
From LeetCode: "Given an array of integers and an integer target, return indices of two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice."
Mathematically, this says
S = A_n + A_m
with n < m. To get this, we check
A_n = S - A_m
having collected a previous value A_n following the check.
Types ¶
This section is empty.
Source Files