A Collection of Essential Go Array Algorithms

array.go

package main

import (
	"fmt"
	"sort"
)

func insertionSort(arr []int) {
	for i := 1; i < len(arr); i++ {
		key := arr[i]
		j := i - 1

		for j >= 0 && arr[j] > key {
			arr[j+1] = arr[j]
			j--
		}
		arr[j+1] = key
	}
	fmt.Println(arr)
}

func bubbleSort(arr []int) {
	swapped := true
	for swapped {
		swapped = false
		for j := 1; j < len(arr); j++ {
			if arr[j] < arr[j-1] {
				arr[j], arr[j-1] = arr[j-1], arr[j]
				swapped = true
			}

		}
	}

	fmt.Println(arr)

}

func removeDuplicates(arr []int) {
	mp := make(map[int]struct{})
	result := []int{}

	for i := 0; i < len(arr); i++ {
		if _, ok := mp[arr[i]]; !ok {
			mp[arr[i]] = struct{}{}
			result = append(result, arr[i])
		}
	}
	bubbleSort(result)

	fmt.Println(result)
}

// twoSum problem can solved using two pointers when and only when arr is sorted
func twoSumSorted(arr []int, target int) {
	left := 0
	right := len(arr) - 1

	res := make([]int, 2)

	for left < right {
		sum := arr[left] + arr[right]
		if sum == target {
			res = []int{left, right} // or left+1, right+1 for 1-based index
			fmt.Println(res)
			return
		} else if sum < target {
			left++
		} else {
			right--
		}
	}

	if len(res) == 0 {
		fmt.Println("no sum found")
	}
}

// for the unsorted arr use the maps for the twoSum problem
func twoSumUnSorted(arr []int, target int) {
	mp := make(map[int]int)

	for i, num := range arr {
		complement := target - num
		if j, ok := mp[complement]; ok {
			fmt.Println([]int{j, i})
			return
		}
		mp[num] = i
	}
	fmt.Println("No pair found")
}

func zeroSumTriplet(arr []int) {
	sort.Ints(arr)
	res := [][]int{}

	for i := 0; i < len(arr)-2; i++ {
		if i > 0 && arr[i] == arr[i-1] {
			continue
		}

		j := i + 1
		k := len(arr) - 1

		for j < k {
			sum := arr[i] + arr[j] + arr[k]

			if sum < 0 {
				j++
			} else if sum > 0 {
				k--
			} else {
				res = append(res, []int{arr[i], arr[j], arr[k]})
				j++
				k--

				for j < k && arr[j] == arr[j-1] {
					j++
				}
				for j < k && arr[k] == arr[k+1] {
					k--
				}
			}
		}
	}

	if len(res) == 0 {
		fmt.Println("No zero sum triplets found.")
	} else {
		for _, triplet := range res {
			fmt.Println(triplet)
		}
	}
}

func reverse(arr []int, start int, end int) {
	for i, j := start, end; i < j; i, j = i+1, j-1 {
		arr[i], arr[j] = arr[j], arr[i]
	}
}

func rotateKSteps(arr []int, steps int) {
	n := len(arr)
	if n == 0 {
		fmt.Println("Array of length 0")
		return
	}

	steps = steps % n
	if steps == 0 {
		fmt.Println(arr)
		return
	}

	reverse(arr, 0, n-1)
	reverse(arr, 0, steps-1)
	reverse(arr, steps, n-1)

	fmt.Println(arr)
}

//	this is one way to solve this
//
// but you cal also solve this by taking the product of all the arr elements and then divide product by each element and save it , you will get the result
func productOfAllExceptSelf(arr []int) {
	n := len(arr)

	if n == 0 {
		fmt.Println("Arr of length 0")
		return
	}

	res := make([]int, n)
	prefix := 1

	for i := 0; i < n; i++ {
		res[i] = 1
	}
	for i := 0; i < n; i++ {
		res[i] = prefix
		prefix *= arr[i]
	}

	postfix := 1
	for i := n - 1; i >= 0; i-- {
		res[i] *= postfix
		postfix *= arr[i]
	}

	fmt.Println(res)
}

func zeroSumTriplets(arr []int) {
	n := len(arr)
	if n == 0 {
		fmt.Println("Array of length 0")
		return
	}

	sort.Ints(arr)

	for i := 0; i < n-2; i++ {
		if i > 0 && arr[i] == arr[i-1] {
			continue
		}

		left, right := i+1, n-1
		for left < right {
			sum := arr[i] + arr[left] + arr[right]

			if sum == 0 {
				fmt.Println([]int{arr[i], arr[left], arr[right]})
				left++
				right--

				for left < right && arr[left] == arr[left-1] {
					left++
				}
				for left < right && arr[right] == arr[right+1] {
					right--
				}
			} else if sum < 0 {
				left++
			} else {
				right--
			}
		}
	}
}

func moveZeroes(nums []int) {
	nonZeroPos := 0

	for i := 0; i < len(nums); i++ {
		if nums[i] != 0 {
			if i != nonZeroPos {
				nums[nonZeroPos], nums[i] = nums[i], nums[nonZeroPos]
			}
			nonZeroPos++
		}
	}

}

func findMaxAverage(nums []int, k int) {
	currSum := 0
	for i := 0; i < k; i++ {
		currSum += nums[i]
	}

	maxSum := currSum

	for i := k; i < len(nums); i++ {
		currSum = currSum + nums[i] - nums[i-k]
		if currSum > maxSum {
			maxSum = currSum
		}
	}

	fmt.Println(float64(maxSum) / float64(k))
}

func main() {
	arr := []int{1, -1, 4, 5, 0}
	//   target := 3

	moveZeroes(arr)
}