How to Circularly Sort an Array in Golang

1 min read 312 words

The challenge

An array is circularly sorted if the elements are sorted in ascending order but displaced, or rotated, by any number of steps.

Complete the function/method that determines if the given array of integers is circularly sorted.

Examples:

These arrays are circularly sorted (true):

[2, 3, 4, 5, 0, 1]       -->  [0, 1] + [2, 3, 4, 5]
[4, 5, 6, 9, 1]          -->  [1] + [4, 5, 6, 9]
[10, 11, 6, 7, 9]        -->  [6, 7, 9] + [10, 11]
[1, 2, 3, 4, 5]          -->  [1, 2, 3, 4, 5]
[5, 7, 43, 987, -9, 0]   -->  [-9, 0] + [5, 7, 43, 987]
[1, 2, 3, 4, 1]          -->  [1] + [1, 2, 3, 4]

While these are not (false):

[4, 1, 2, 5]
[8, 7, 6, 5, 4, 3]
[6, 7, 4, 8]
[7, 6, 5, 4, 3, 2, 1]

The solution in Golang

Option 1:

package solution
func IsCircleSorted(r []int) bool {
    downs := 0
    for i:= 0; i<len(r); i ++ {
      if r[i] > r[(i+1)%len(r)] {
      downs += 1}
    }
    return downs <= 1
}

Option 2:

package solution
import "sort"
func IsCircleSorted(r []int) bool {
  q := make([]int, len(r))
  for i := 0; i < len(r); i++ {
    for j := 0; j < len(r); j++ {
      q[j] = r[(j+i)%len(r)]
    }
    if sort.IntsAreSorted(q) {
      return true
    }
  }
  return len(r) == 0
}

Option 3:

package solution
func IsCircleSorted(r []int) bool {
  if len(r) == 0 {
    return true
  }
  decreaseCount := 0
  for i := 1; i < len(r); i++ {
    if r[i-1] > r[i] {
      decreaseCount++
    }
  }
  if r[len(r)-1] > r[0] {
    decreaseCount++
  }
  return decreaseCount <= 1
}

Test cases to validate our solution

package solution_test
import (
    . "github.com/onsi/ginkgo"
    . "github.com/onsi/gomega"
)
var _ = Describe("Example Tests",func() {
    It("Test 1",func() {Expect(IsCircleSorted([]int{2,3,4,5,6})).To(Equal(true))})
    It("Test 2",func() {Expect(IsCircleSorted([]int{6,2,3,4,5})).To(Equal(true))})
    It("Test 3",func() {Expect(IsCircleSorted([]int{3,2,4,5,6})).To(Equal(false))})
})
Tags:
Andrew
Andrew

Andrew is a visionary software engineer and DevOps expert with a proven track record of delivering cutting-edge solutions that drive innovation at Ataiva.com. As a leader on numerous high-profile projects, Andrew brings his exceptional technical expertise and collaborative leadership skills to the table, fostering a culture of agility and excellence within the team. With a passion for architecting scalable systems, automating workflows, and empowering teams, Andrew is a sought-after authority in the field of software development and DevOps.

Tags

Recent Posts