[Go] Array and String - Array Partition I

import "sort"
func min(x,y int) int{
    if x < y {
        return x
    }
    return y
}
func arrayPairSum(nums []int) int {

    answer := 0
    sort.Slice(nums, func(i,j int) bool { return nums[i] < nums[j] })
    //fmt.Printf("%v\n", nums)
    for i := 0; i < len(nums); i+=2 {
        answer += min(nums[i], nums[i+1])
    }
    
    return answer
}

Given an integer array nums of 2n integers, group these integers into n pairs (a1, b1), (a2, b2), ..., (an, bn) such that the sum of min(ai, bi) for all i is maximized. Return the maximized sum.

 

Example 1:

Input: nums = [1,4,3,2]
Output: 4
Explanation: All possible pairings (ignoring the ordering of elements) are:
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
So the maximum possible sum is 4.

Example 2:

Input: nums = [6,2,6,5,1,2]
Output: 9
Explanation: The optimal pairing is (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9.

 

Constraints:

• 1 <= n <= 104
• nums.length == 2 * n
• -104 <= nums[i] <= 104

My code

func arrayPairSum(nums []int) int {
	length := len(nums)
	sum := 0
	maxi := 0
	counter := 0
	for length > 0 {
		max := math.MinInt
		for i := 0; i < length; i++ {
			if max <= nums[i] {
				max = nums[i]
				maxi = i
			}
		}

		nums = append(nums[:maxi], nums[maxi+1:]...)
		counter++
		length--
		if counter%2 == 0 {
			sum += max
		}

	}
	return sum
}

• I didn't want to use sort function so I implemented like upper.
• length will have nums length.
• sum will be the return value.
• maxi will be the temp of max index.
• counter is used for sum.
• for loop will run until length will be minus.
• max variable will store greater number in array.
• second for loop will run during i reaches to length.
• if condition checks max value. 
• When max is decieded, index also will be stored in maxi.
• After second for loop, max index will be removed from array.
• counter increases and length decreases
• when counter is even, sum will be added by max.
• return sum.

sample 48 ms submission

func arrayPairSum(nums []int) int {
    sort.Ints(nums)
    
    sum := 0
    for i:=0; i<len(nums); i+=2 {
        sum += nums[i]
    }
    return sum
}

• This code is simple with using sort.
• the first of the line, nums will be sorted.
• sum will be declared.
• every odd sequence of array will be added.
• (1, 2) (3, 4) = 4
• (1, 2) (2, 5) (6, 6) = 9

sample 49 ms submission

func arrayPairSum(nums []int) int {
    arr := make([]int, 20001)
    for _, v := range nums {
        arr[v+10000]++
    }
    var sum int
    flag := true
    for i := 0; i < len(arr); i++ {
        for arr[i] > 0 {
            if flag {
                sum += (i - 10000)
            }
            flag = !flag
			arr[i]--
        }
    }
    return sum
}

• This code checks frequency of numbers.
• so it has 20,001 space for it including negative numbers.(-10,000 ~ 10,000)
• flag will have true
• for loop will run to 20,001.
• next for loop will run until arr[i] is 0.
• flag works like i+2 like before. 
• when flag is true, sum will be added or not arr[i] will decrease without anything.
• later sum will be return.
• algorithm is quite simple but size is big.

sample 52 ms submission

func min(x, y int) int {
	if x < y {
		return x
	}

	return y
}

func arrayPairSum(nums []int) int {
	sort.Ints(nums)

	sum := 0

	for i, j := 0, 1; j < len(nums); i, j = i+2, j+2 {
		sum += min(nums[i], nums[j])
	}

	return sum
}

sample 55 ms submission

func arrayPairSum(nums []int) int {
    
sort.Ints(nums)
	
	max_sum := 0
	i := len(nums) - 1
	for {
		if i > 0 {
			max_sum += nums[i-1]
			i = i - 2
		} else {
			break
		}

	}
	return max_sum
}

sample 57 ms submission

import "sort"
func min(x,y int) int{
    if x < y {
        return x
    }
    return y
}
func arrayPairSum(nums []int) int {

    answer := 0
    sort.Slice(nums, func(i,j int) bool { return nums[i] < nums[j] })
    //fmt.Printf("%v\n", nums)
    for i := 0; i < len(nums); i+=2 {
        answer += min(nums[i], nums[i+1])
    }
    
    return answer
}