LeetCode 28 is another very easy problem. You are given two strings, and you have to see if the second string exists in the first string. If so, return the index of the start of that string. If it can’t be found, return -1. Solution 1: strings.Index This kind of problem is so common in programming, that the majority of standard libraries include it. In C, you can use strstr. In Go, you can use strings.Index(). ...
LeetCode 27 is, like the last problem, an easy problem. The problem itself is to remove elements from an array that equal v. Here is an example: Input: nums = [1,2,3,1,2], val = 1 Output: nums = [2,3,2,_,_], size = 3 If you read the post for problem 26, then I think you’ll know the solution. func removeElement(nums []int, val int) int { write_index := 0 for _, v := range nums { if val != v { nums[write_index] = v write_index++ } } return write_index } write_index tracks where the next kept element goes, so each value that isn’t val gets compacted toward the front while everything else is skipped. If the code doesn’t make sense, then I recommend that you read the last post. ...
Problem 26 lives up to its label: easy. You are given a sorted array, and you have to remove duplicates from it. It also asks that you include the number of unique elements in the array. Here are some samples. Input: [1,1,2] Output: 2, nums = [1,2,_] The first solution I came up with was to find duplicates and remove them from the array: func removeDuplicates(nums []int) int { for i := 0; i < len(nums) - 1; i++ { j := i + 1 if nums[i] == nums[j] { j++ for ; j < len(nums) && nums[i] == nums[j]; j++ { } nums = slices.Delete(nums, i+1,j) } } return len(nums) } This, though, is O(n²). The reason why is not the two for loops, it is the slices.Delete, which will shift all the elements from the right over to the left. We can avoid this cost and get the solution down to just O(n) by not shifting. ...
Welcome back. We are going to be solving a dreaded HARD problem. Specifically, we are going to do problem 25. What I like about it is that it directly builds on problem 24, the problem I solved yesterday. As a reminder, problem 24 asked you to swap nodes in pairs. This problem is the same idea, except instead of pairs, we have to swap k nodes. Meaning, problem 24 was a specific instance of this problem where k=2. To help, here are two examples: ...
LeetCode 24 is a problem where you have to swap pairs of nodes in a linked list. I think the examples are more informative than the text, so here are the examples but I did modify them to use linked list notation: Example 1: Input: 1 -> 2 -> 3 -> 4 Output: 2 -> 1 -> 4 -> 3 Example 2: Input: nil Output: nil Example 3: Input: 1 Output: 1 Example 4: Input: 1 -> 2 -> 3 Output: 2 -> 1 -> 3 This post will be shorter than the others in the series. Despite being listed as medium difficulty, there wasn’t anything that I found interesting. ...
LeetCode 23 is the first problem in the series that covers a HARD problem. Should be challenging, right? Well, let’s see. To start, I need to define the problem. You get a list of linked lists that are sorted. You have to merge them all into one big linked list, that is also sorted. That’s it. Solution 1: Screw Linked Lists I don’t have anything against linked lists. They’re cool. However, sorting an array is a solved problem. So, if everything was in just one big slice, then we’d be done. ...
Welcome back. This time we are going to work on problem 22. The idea is simple. We need to generate every possible valid string of open and closed parenthesis for an integer n. The example they give is for n=1 and n=3: Input: n = 1 Output: ["()"] Input: n = 3 Output: ["((()))","(()())","(())()","()(())","()()()"] Failed Attempt func generateParenthesis(n int) []string { var strings []string switch n { case 0: // do nothing case 1: strings = append(strings, "()") default: old_strings := generateParenthesis(n - 1) for _, o := range old_strings { strings = append(strings, "()" + o) strings = append(strings, "(" + o + ")") } } return strings } This was my first solution, but it failed. The reason why can be shown with n=3, where it can’t generate the string “(())()”. This may lead you to think that you should add one more line in the for loop: strings = append(strings, o + "()"). This, though, will cause duplicate strings, which breaks the rules. So, after that we could go the de-duplication route like we did for #18, but I’d rather not. So, let’s abandon this solution and go to the smarter approach. ...
Unfortunately, LeetCode 21 had no interesting wrinkles to explore. func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode { if list1 == nil { return list2 } else if list2 == nil { return list1 } var head *ListNode if list1.Val <= list2.Val { head = list1 list1 = list1.Next } else { head = list2 list2 = list2.Next } cur := head for list1 != nil && list2 != nil { if list1.Val <= list2.Val { cur.Next = list1 list1 = list1.Next } else { cur.Next = list2 list2 = list2.Next } cur = cur.Next } if list1 == nil { cur.Next = list2 } else if list2 == nil { cur.Next = list1 } return head } There is one way to reduce the amount of code, which is to create a dummy variable like so: ...
LeetCode 20 gives you a string made up of the six bracket characters ()[]{} and asks whether they are properly matched and nested. “Properly” means every opener has a corresponding closer of the same type, and they close in the right order. So ()[]{} is valid, ([]) is valid, but ([)] is not. Anywho, I’ll start with a dumb implementation for fun and then move on to the better but less exciting version. ...
LeetCode 19 asks the solver to remove a node from a linked list. It does have a trick, though. Rather than the typical “remove the nth element” it gives you an index based on the end of the list, “remove the nth element from the end of the list.” That framing is the whole problem. In a singly linked list you can only move forward, so “nth from the end” isn’t something you can read off directly the way you would in an array. Every solution below is really just a different way of figuring out which node sits before the one you want to drop, since removing a node means pointing its predecessor’s Next past it. ...