Advanced Array-Based Problem-Solving with LeetCode Examples in Go-Part-2.

ยท

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://medium.com/techwasti