s189: do it in-place with O(1) extra space

legolas.zhan · legolas.zhan · commit b0e40f34e43c · 2024-08-14T14:31:50.000+08:00
diff --git a/leetcode/array/rotate.go b/leetcode/array/rotate.go
@@ -39,6 +39,7 @@ Try to come up as many solutions as you can, there are at least 3 different ways
 
 package larray
 
+/*
 func rotate(nums []int, k int) {
 	n := len(nums)
 	c := make([]int, n)
@@ -50,3 +51,25 @@ func rotate(nums []int, k int) {
 		nums[(i+k)%n] = v
 	}
 }
+*/
+
+func rotate(nums []int, k int) {
+	n := len(nums)
+	k = k % n
+	if k == 0 {
+		return
+	}
+
+	var reverse func(nums []int, start, end int)
+	reverse = func(nums []int, start, end int) {
+		for start < end {
+			nums[start], nums[end] = nums[end], nums[start]
+			start++
+			end--
+		}
+	}
+
+	reverse(nums, 0, n-1) // Reverse the entire array
+	reverse(nums, 0, k-1) // Reverse the first k elements
+	reverse(nums, k, n-1) // Reverse the remaining n - k elements
+}
