Array101 Merge Sorted Array in GO

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

Constraints:

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -109 <= nums1[i], nums2[j] <= 109

func merge(nums1 []int, m int, nums2 []int, n int) {
    temp := make([]int, 0)
    i := 0
    j := 0
    for i+j < m+n {
        if j >= n {
            temp = append(temp, nums1[i])
            i++
        } else if i >= m {
            temp = append(temp, nums2[j])
            j++
        } else if nums1[i] > nums2[j] {
            temp = append(temp, nums2[j])
            j++
        } else {
            temp = append(temp, nums1[i])
            i++
        }
    }
    if n == 0 {
        return
    }
    copy(nums1, temp)
}

https://go.dev/play/p/X6e7aR7hwfG

Go Playground - The Go Programming Language

 

- At first I had problem with solving problem. Becuase I didn't read the problem well. So I just sorted result. I ignored arguments about m or n.

- Today, I read the problem again. I realized that Leetcode gave arguments which valid numbers not length.

- After noticing, I changed all code and finally I got accepted.

- The bad was me and the leetcode was right.

sample 0 ms submission & sample 2200 KB submission

func merge(nums1 []int, m int, nums2 []int, n int)  {
  for m > 0 && n > 0 {
    if nums1[m-1] < nums2[n-1] {
      shift(nums1, m)
      nums1[m] = nums2[n-1]
      n--
      m++
    }else{
      m--
    }
  }
  if m == 0 {
    for n > 0 {
      shift(nums1, 0)
      nums1[0] = nums2[n-1]
      n--
    }      
  }
}
 
func shift(arr []int, index int) {
  length := len(arr) - 1
  for i := length; i >= index; i-- {
    if i + 1 <= length {
      arr[i+1] = arr[i]
    }
  }
}

func merge(nums1 []int, m int, nums2 []int, n int)  {
  for m > 0 && n > 0 {
//is nums2 bigger & equal will be better 
//because we don't need to check less if value is same.
    if nums1[m-1] <= nums2[n-1] {  
      shift(nums1, m)
      nums1[m] = nums2[n-1]
      n--
      m++
    }else{
      m--
    }
  }
  if m == 0 {
    for n > 0 {
      shift(nums1, 0)
      nums1[0] = nums2[n-1]
      n--
    }      
  }
}
 
func shift(arr []int, index int) {
  length := len(arr) - 1
  for i := length; i >= index; i-- {
    if i + 1 <= length {
      arr[i+1] = arr[i]
    }
  }
}
 

- I modified this code for more effictively.

- This code firstly check m and n value is 0. If not, check both end array(biggest number in array). So if Nums2 is bigger or same with end of Nums1 values, Shift values from end of array to checked value. After this, bigger or same value will be input in next array from checked value(first time, it is empty). increment m and decrement n. if nums1 is bigger than nums2 value, find smaller or same value than nums2. 
- If m will be 0, that means, nums2 has smaller value than nums1, so push every array to make nums1[0] values move to nums1[1] so that nums2 smaller value can be input until nums2 array index will be zero.

 

sample 1 ms submission 

func merge(nums1 []int, m int, nums2 []int, n int)  {
    
    
    p := m+n-1
    m--
    n--
    fmt.Println(m,n,p)
    
    for m >=0 && n >= 0{
        
        if nums1[m] > nums2[n]{
            nums1[p] = nums1[m]
            m--
        }else{
            nums1[p] = nums2[n]
            n--
        }
        p--
        
    }
    
    for m >=0{
        nums1[p] = nums1[m]
        m--
        p--
    }
    for n >= 0{
        nums1[p] = nums2[n]
        n--
        p--
    }
    
    // fmt.Println(nums1)
    
}

sample 2200 KB submission

func merge(nums1 []int, m int, nums2 []int, n int)  {
    m -= 1
    n -= 1
    
    for p := len(nums1) - 1; p >= 0; p-- {
        if m < 0 || n < 0 {
            break
        }
        
        if nums1[m] >= nums2[n] {
            nums1[p] = nums1[m]
            m -= 1
        } else {
            nums1[p] = nums2[n]
            n -= 1
        }
    }
    
    // Copy any remainders from nums2
    for q := n; q >=0; q-- {
        nums1[q] = nums2[n]
        n -= 1
    }  
    
}