Nerd For Tech
Published in

Nerd For Tech

Swift Leetcode Series : Beautiful Arrangement II

April Leetcode Challenge : Day 12 ( Leetcode #667 Medium)

You can also read the full story on The Swift Nerd blog with the link above to find more about it in other languages.

Problem Statement

Given two integers n and k, you need to construct a list which contains n different positive integers ranging from 1 to 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.

Examples

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.

Constraints

  1. The n and k are in the range 1 <= k < n <= 104.

Solution

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.

Complexity Analysis

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.

Thank you for reading. If you liked this article and found it useful, share and spread it like wildfire!

You can find me on TheSwiftNerd | LinkedIn | Github

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store