Swift Leetcode Series : Beautiful Arrangement II
April Leetcode Challenge : Day 12 ( Leetcode #667 Medium)
Beautiful Arrangement II (Leetcode 667) -
Difficulty : Link : April Leetcoding Challenge 2021: Day 12 Given two integers n and k, you need to construct a list…
You can also read the full story on The Swift Nerd blog with the link above to find more about it in other languages.
Given two integers
k, you need to construct a list which contains
n different positive integers ranging from
n and obeys the following requirement:
Suppose this list is [a1, a2, a3, … , an], then the list [|a1 – a2|, |a2 – a3|, |a3 – a4|, … , |an-1 – an|] has exactly
k distinct integers.
If there are multiple answers, print any of them.
Input: n = 3, k = 1
Output: [1, 2, 3]
Explanation: The [1, 2, 3] has three different positive integers ranging from 1 to 3, and the [1, 1] has exactly 1 distinct integer: 1.Input: n = 3, k = 2
Output: [1, 3, 2]
Explanation: The [1, 3, 2] has three different positive integers ranging from 1 to 3, and the [2, 1] has exactly 2 distinct integers: 1 and 2.
kare in the range 1 <= k < n <= 104.
The problem is a bit tricky but we will try to find out a pattern. When k = 1, it means that in lists of |a1 — a2|, |a2 — a3|, |a3 — a4|, … , |an-1 — an|, there can be only 1 distinct element. Since we numbers have be to in range of [1, n], they all have same difference of 1, which is distinct. So for K = 1, we can simple return the series [1, n] in either increasing or decreasing manner i.e [1,2,3 … N] or [N, N-1, … 1].
The problem becomes more tricky, when k is large. For range of [1, n], the maximum difference possible is n-1. And since minimum difference is 1 ,so differences would be in range of [1, n- 1]. The thing here to note is that max value of k is n — 1. Let’s take n = 5 and k = 4 for example. The only possible way to get the absolute difference of 4 would be for 1 and 5 to be consecutive. After that there are two possibilites for next smallest absolute difference of 3, which are 1 & 4 or 2 & 5. Since the 1 and 5 are already next to each other, that means we can achieve this second step with either [1,5,2] or [4,1,5] .
We can observe that we can obtain the result by alternatively appending or zig-zagging (sounds cool!) the the two extreme possible values. After we have inserted the k values , we can insert the result of the (n — k) values by simply incrementing.
To fill the values in zig-zag order, we can take left and right values in the first part [1, k + 1]. We can use the module operation (i % 2) to increment them alternatively. Both the pointers would move towards each other (Left ++ and right — ) and we will iterate till we have filled k values which marks our first pass. For second pass, we can simple loop from k + 1 to n and fill i +1 (because i is 0 based and the range of values should be [0, n] ).
There is an interesting discussion forum on this leetcode where i got the idea for the solution.
Time = O(N). We are iterating twice for building our pattern once for 1 to k + 1 and then for k + 2 to n. Total work done is 2*N, which is O(N) asymptotically.
Space = O(1). We have taken an output array but it is strictly because of the requirement of the question. We could have otherwise outputted directly on the console and it would be perfect too.