Advanced Array-Based Problem-Solving with LeetCode Examples in Go-Part-2.
Table of contents
Problem 1: Best Time to Buy and Sell Stock II
Problem Statement: You are given an array prices where prices[i] is the price of a given stock on the i-th day. Find the maximum profit you can achieve by buying and selling stocks multiple times. You may complete as many transactions as you like, but you must sell the stock before you buy again.
Solution:
func maxProfit(prices []int) int {
maxProfit := 0
for i := 1; i < len(prices); i++ {
if prices[i] > prices[i-1] {
maxProfit += prices[i] - prices[i-1]
}
}
return maxProfit
}
Problem 2: Container With Most Water
Problem Statement: Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i are at (i, ai) and (i, 0). Find two lines, which, together with the x-axis, forms a container that holds the most water.
Solution:
func maxArea(height []int) int {
maxArea, left, right := 0, 0, len(height)-1
for left < right {
currentArea := min(height[left], height[right]) * (right - left)
maxArea = max(maxArea, currentArea)
if height[left] < height[right] {
left++
} else {
right--
}
}
return maxArea
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
Problem 3: Rotate Image
Problem Statement: You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees (clockwise).
Solution:
func rotate(matrix [][]int) {
n := len(matrix)
for i := 0; i < n/2; i++ {
for j := i; j < n-i-1; j++ {
temp := matrix[i][j]
matrix[i][j] = matrix[n-1-j][i]
matrix[n-1-j][i] = matrix[n-1-i][n-1-j]
matrix[n-1-i][n-1-j] = matrix[j][n-1-i]
matrix[j][n-1-i] = temp
}
}
}
Problem 4: Jump Game
Problem Statement: You are given an array of non-negative integers nums, where each element represents your maximum jump length at that position. Determine if you can reach the last index.
Solution:
func canJump(nums []int) bool {
lastPos := len(nums) - 1
for i := len(nums) - 1; i >= 0; i-- {
if i+nums[i] >= lastPos {
lastPos = i
}
}
return lastPos == 0
}
Problem 5: Merge Intervals
Problem Statement: Given an array of n intervals where intervals[i] = [starti, endi], merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.
Solution:
func merge(intervals [][]int) [][]int {
sort.Slice(intervals, func(i, j int) bool {
return intervals[i][0] < intervals[j][0]
})
merged := [][]int{}
for _, interval := range intervals {
if len(merged) == 0 || merged[len(merged)-1][1] < interval[0] {
merged = append(merged, interval)
} else {
merged[len(merged)-1][1] = max(merged[len(merged)-1][1], interval[1])
}
}
return merged
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
Problem 6: Next Permutation
Problem Statement: Implement nextPermutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
Solution:
func nextPermutation(nums []int) {
i := len(nums) - 2
for i >= 0 && nums[i] >= nums[i+1] {
i--
}
if i >= 0 {
j := len(nums) - 1
for j >= 0 && nums[j] <= nums[i] {
j--
}
nums[i], nums[j] = nums[j], nums[i]
}
reverse(nums[i+1:])
}
func reverse(nums []int) {
left, right := 0, len(nums)-1
for left < right {
nums[left], nums[right] = nums[right], nums[left]
left++
right--
}
}
Problem 7: Spiral Matrix
Problem Statement: Given an m x n matrix, return all elements of the matrix in spiral order.
Solution:
func spiralOrder(matrix [][]int) []int {
var result []int
m, n := len(matrix), len(matrix[0])
top, bottom, left, right := 0, m-1, 0, n-1
for len(result) < m*n {
for i := left; i <= right && len(result) < m*n; i++ {
result = append(result, matrix[top][i])
}
top++
for i := top; i <= bottom && len(result) < m*n; i++ {
result = append(result, matrix[i][right])
}
right--
for i := right; i >= left && len(result) < m*n; i-- {
result = append(result, matrix[bottom][i])
}
bottom--
for i := bottom; i >= top && len(result) < m*n; i-- {
result = append(result, matrix[i][left])
}
left++
}
return result
}
Problem 8: Search in Rotated Sorted Array
Problem Statement: Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. You are given a target value to search. If found in the array, return its index; otherwise, return -1.
Solution:
func search(nums []int, target int) int {
left, right := 0, len(nums)-1
for left <= right {
mid := left + (right-left)/2
if nums[mid] == target {
return mid
}
if nums[left] <= nums[mid] {
if nums[left] <= target && target < nums[mid] {
right = mid - 1
} else {
left = mid + 1
}
} else {
if nums[mid] < target && target <= nums[right] {
left = mid + 1
} else {
right = mid - 1
}
}
}
return -1
}
Problem 9: Three Sum
Problem Statement: Given an integer array nums, return all the unique triplets [nums[i], nums[j], nums[k]] such that i != j != k and nums[i] + nums[j] + nums[k] = 0.
Solution:
func threeSum(nums []int) [][]int {
sort.Ints(nums)
result := [][]int{}
for i := 0; i < len(nums)-2; i++ {
if i == 0 || (i > 0 && nums[i] != nums[i-1]) {
left, right, target := i+1, len(nums)-1, 0-nums[i]
for left < right {
if nums[left]+nums[right] == target {
result = append(result, []int{nums[i], nums[left], nums[right]})
for left < right && nums[left] == nums[left+1] {
left++
}
for left < right && nums[right] == nums[right-1] {
right--
}
left++
right--
} else if nums[left]+nums[right] < target {
left++
} else {
right--
}
}
}
}
return result
}
Problem 10: Subarray Sum Equals K
Problem Statement: Given an array of integers nums and an integer k, return the total number of continuous subarrays whose sum equals to k.
Solution:
func subarraySum(nums []int, k int) int {
sumCount := make(map[int]int)
sumCount[0] = 1
count, sum := 0, 0
for _, num := range nums {
sum += num
count += sumCount[sum-k]
sumCount[sum]++
}
return count
}
These solutions illustrate advanced array-based problems frequently encountered on platforms like LeetCode, showcasing effective problem-solving techniques using Go. Practicing these problems strengthens algorithmic thinking and equips developers with diverse strategies to solve array-related challenges effectively.
I hope this helps, you!!
More such articles:
https://www.youtube.com/@maheshwarligade