Array Tips and Tricks: LeetCode Solutions
A collection of LeetCode array and string problems with detailed explanations and Go solutions, including Longest Common Prefix, Zigzag Conversion, Trapping Rain Water, and more.
Array Tips and Tricks: LeetCode Solutions
A collection of LeetCode array and string problems with detailed explanations and Go solutions.
Longest Common Prefix
Problem: Find the longest common prefix string amongst an array of strings.
Approach: Start with the first element in the array and iterate through the remaining elements, removing letters that are not present in them.
// Solution with built-in functions
func longestCommonPrefix(strs []string) string {
prefix := strs[0]
for i := 1; i < len(strs); i++ {
for !strings.HasPrefix(strs[i], prefix) {
prefix = prefix[:len(prefix)-1]
}
}
return prefix
}
// Raw solution
func longestCommonPrefix(strs []string) string {
if len(strs) == 0 {
return ""
}
prefix := ""
for idx := 0; idx < len(strs[0]); idx++ {
letter := string(strs[0][idx])
flag := true
for _, v := range strs {
if idx < len(v) {
if string(v[idx]) != letter {
flag = false
break
}
} else {
flag = false
}
}
if flag == false {
break
}
prefix += letter
}
return prefix
}
Reverse Words in a String
Problem: Given an input string s, reverse the order of the words.
A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.
Return a string of the words in reverse order concatenated by a single space.
Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.
Example 1:
Input: s = "the sky is blue"
Output: "blue is sky the"
func reverseWords(s string) string {
var ress []string
res := strings.Split(s, " ")
for i := len(res) - 1; i >= 0; i-- {
if res[i] == " " || res[i] == "" {
continue
} else {
ress = append(ress, res[i])
}
}
return strings.Join(ress, " ")
}
Zigzag Conversion
Problem: The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this:
P A H N
A P L S I I G
Y I R
And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows.
Example 1:
Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
Example 2:
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P I N
A L S I G
Y A H R
P I
func convert(s string, numRows int) string {
if numRows == 1 {
return s
}
stringSlice := make([]string, numRows)
ptr, reverse := 0, false
for idx := 0; idx < len(s); idx++ {
ss := string(s[idx])
stringSlice[ptr] += ss
if ptr == numRows-1 {
reverse = true
ptr -= 1
continue
}
if !reverse {
ptr += 1
}
if ptr == 0 {
reverse = false
ptr += 1
continue
}
if reverse {
ptr -= 1
}
}
finalStr := ""
for _, v := range stringSlice {
finalStr += v
}
stringSlice = nil
return finalStr
}
Find the Index of the First Occurrence in a String
Problem: Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Example 1:
Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Explanation: "sad" occurs at index 0 and 6.
The first occurrence is at index 0, so we return 0.
Example 2:
Input: haystack = "leetcode", needle = "leeto"
Output: -1
Explanation: "leeto" did not occur in "leetcode", so we return -1.
// Naive Solution
func strStr(haystack string, needle string) int {
return strings.Index(haystack, needle)
}
// KMP Algorithm with Longest Prefix Suffix array
func strStr(haystack string, needle string) int {
if len(needle) == 0 {
return 0
}
lps := computeLps(needle)
ptrH := 0
ptrN := 0
for ptrH < len(haystack) {
if haystack[ptrH] == needle[ptrN] {
ptrH++
ptrN++
} else {
if ptrN != 0 {
ptrN = lps[ptrN-1]
} else {
ptrH++
}
}
if ptrN == len(needle) {
return ptrH - ptrN
}
}
return -1
}
func computeLps(pattern string) []int {
length := 0
lps := make([]int, len(pattern))
i := 1
for i < len(pattern) {
if pattern[i] == pattern[length] {
length++
lps[i] = length
i++
} else {
if length != 0 {
length = lps[length-1]
} else {
lps[i] = 0
i++
}
}
}
return lps
}
Hard LeetCode Problems
Trapping Rain Water
Problem: Trapping Rain Water
Find the water trapped between the heights.
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Approach: We can use two pointers or a stack. The stack approach is easier to understand:
- Start with a left wall (first element is pushed to the stack)
- If the current element is less than the stack top, push it onto the stack
- If the current element is greater than the stack top, pop the stack top until we get a left wall and calculate the area covered. We only pop until
height[i] > stack[top] - Each time we pop, we calculate the height between the left and right walls. Since we only push items which are less than the stack values, we can assume the element that we popped will be less than the stack top
Example: [4,2,1,3]
We keep pushing to the stack until we reach 3, then we pop 1 and calculate the area between index 3 and index 1. We can see that 1 will be the lowest point between the two walls.
func trap(height []int) int {
var s []int
area := 0
for i := 0; i < len(height); i++ {
for len(s) > 0 && height[i] > height[s[len(s)-1]] {
top := s[len(s)-1]
s = s[:len(s)-1]
if len(s) == 0 {
break
}
distance := i - s[len(s)-1] - 1
boundingHeight := min(height[s[len(s)-1]], height[i]) - height[top]
area += distance * boundingHeight
}
s = append(s, i)
}
return area
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
Candy
Problem: Candy
Problem: Calculate the minimum candies needed to give to kids based on their ratings.
Approach: We make two passes through the array - one from the left and one from the right - to determine how many candies are needed.
func candy(ratings []int) int {
n := len(ratings)
candies := make([]int, n)
for i := range candies {
candies[i] = 1
}
// Left to right pass
for i := 1; i < n; i++ {
if ratings[i] > ratings[i-1] {
candies[i] = candies[i-1] + 1
}
}
// Right to left pass
for i := n - 2; i >= 0; i-- {
if ratings[i] > ratings[i+1] {
if candies[i] <= candies[i+1] {
candies[i] = candies[i+1] + 1
}
}
}
totalCandies := 0
for _, candy := range candies {
totalCandies += candy
}
return totalCandies
}
Text Justification
Problem: Given an array of strings words and a width maxWidth, format the text such that each line has exactly maxWidth characters and is fully (left and right) justified.
You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly maxWidth characters.
Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line does not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.
For the last line of text, it should be left-justified, and no extra space is inserted between words.
Note:
- A word is defined as a character sequence consisting of non-space characters only.
- Each word's length is guaranteed to be greater than
0and not exceedmaxWidth. - The input array
wordscontains at least one word.
Example 1:
Input: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
Output:
[
"This is an",
"example of text",
"justification. "
]
Example 2:
Input: words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16
Output:
[
"What must be",
"acknowledgment ",
"shall be "
]
Explanation: Note that the last line is "shall be " instead of "shall be", because the last line must be left-justified instead of fully-justified.
Note that the second line is also left-justified because it contains only one word.
Example 3:
Input: words = ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"], maxWidth = 20
Output:
[
"Science is what we",
"understand well",
"enough to explain to",
"a computer. Art is",
"everything else we",
"do "
]
func fullJustify(words []string, maxWidth int) []string {
result := []string{}
n := len(words)
left := 0 // start index of the current line
for left < n {
// Determine how many words fit in the current line
right := findRight(words, maxWidth, left)
// Justify words[left:right]
line := justifyLine(words, left, right, maxWidth)
result = append(result, line)
// Move to the next line
left = right + 1
}
return result
}
func justifyLine(words []string, left, right, maxWidth int) string {
// If the line contains only one word, left-justify it
if left == right {
return words[left] + spaces(maxWidth-len(words[left]))
}
// Check if this is the last line
isLastLine := right == len(words)-1
// Count total length of words in this line
totalWordLen := 0
for i := left; i <= right; i++ {
totalWordLen += len(words[i])
}
// Total spaces we need to distribute
totalSpaces := maxWidth - totalWordLen
gaps := right - left // number of gaps between words
// Space distribution
spacePerGap := totalSpaces / gaps
extraSpaces := totalSpaces % gaps
// Last line should be left-justified
if isLastLine {
spacePerGap = 1
extraSpaces = 0
}
var builder strings.Builder
for i := left; i <= right; i++ {
builder.WriteString(words[i])
// Add spaces after each word except the last
if i < right {
builder.WriteString(spaces(spacePerGap))
// Distribute extra spaces from left to right
if extraSpaces > 0 {
builder.WriteString(" ")
extraSpaces--
}
}
}
// Pad remaining spaces at the end (only needed for last line)
remaining := maxWidth - builder.Len()
if remaining > 0 {
builder.WriteString(spaces(remaining))
}
return builder.String()
}
func findRight(words []string, maxWidth int, left int) int {
right := left
lineLen := 0
for right < len(words) {
// +1 accounts for the space between words
if lineLen+len(words[right])+(right-left) > maxWidth {
break
}
lineLen += len(words[right])
right++
}
return right - 1
}
func spaces(count int) string {
if count <= 0 {
return ""
}
return strings.Repeat(" ", count)
}