Solution by awice


  • 1

    Approach #1: Brute Force [Time Limit Exceeded]

    Intuition

    For each permutation of [1, 2, ..., n], let's look at the set of differences of the adjacent elements.

    Algorithm

    For each permutation, we find the number of unique differences of adjacent elements. If it is the desired number, we'll return that permutation.

    To enumerate each permutation without using library functions, we use a recursive algorithm, where permute is responsible for permuting the indexes of nums in the interval [start, nums.length).

    Python

    class Solution(object):
        def constructArray(self, n, k):
            seen = [False] * n
            def num_uniq_diffs(arr):
                ans = 0
                for i in range(n):
                    seen[i] = False
                for i in range(len(arr) - 1):
                    delta = abs(arr[i] - arr[i+1])
                    if not seen[delta]:
                        ans += 1
                        seen[delta] = True
                return ans
    
            for cand in itertools.permutations(range(1, n+1)):
                if num_uniq_diffs(cand) == k:
                    return cand
    

    Java

    class Solution {
        private ArrayList<ArrayList<Integer>> permutations(int[] nums) {
            ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
            permute(ans, nums, 0);
            return ans;
        }
    
        private void permute(ArrayList<ArrayList<Integer>> ans, int[] nums, int start) {
            if (start >= nums.length) {
                ArrayList<Integer> cur = new ArrayList<Integer>();
                for (int x : nums) cur.add(x);
                ans.add(cur);
            } else {
                for (int i = start; i < nums.length; i++) {
                    swap(nums, start, i);
                    permute(ans, nums, start+1);
                    swap(nums, start, i);
                }
            }
        }
    
        private void swap(int[] nums, int i, int j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    
        private int numUniqueDiffs(ArrayList<Integer> arr) {
            boolean[] seen = new boolean[arr.size()];
            int ans = 0;
    
            for (int i = 0; i < arr.size() - 1; i++) {
                int delta = Math.abs(arr.get(i) - arr.get(i+1));
                if (!seen[delta]) {
                    ans++;
                    seen[delta] = true;
                }
            }
            return ans;
        }
    
        public int[] constructArray(int n, int k) {
            int[] nums = new int[n];
            for (int i = 0; i < n; i++) {
                nums[i] = i+1;
            }
            for (ArrayList<Integer> cand : permutations(nums)) {
                if (numUniqueDiffs(cand) == k) {
                    int[] ans = new int[n];
                    int i = 0;
                    for (int x : cand) ans[i++] = x;
                    return ans;
                }
            }
            return null;
        }
    }
    

    Complexity Analysis

    • Time Complexity: $$O(n!)$$ to generate every permutation in the outer loop, then $$O(n)$$ work to check differences. In total, $$O(n * n!)$$.

    • Space Complexity: $$O(n)$$. We use seen to store whether we've seen the differences, and each generated permutation is length n.


    Approach #2: Construction [Accepted]

    Intuition

    When k = n-1, a valid construction is [1, n, 2, n-1, 3, n-2, ....]. One way to see this is, we need to have a difference of n-1, which means we need 1 and n adjacent; then, we need a difference of n-2, etc.

    Also, when k = 1, a valid construction is [1, 2, 3, ..., n]. So we have a construction when n-k is tiny, and when it is large. This leads to the idea that we can stitch together these two constructions: we can put [1, 2, ..., n-k-1] first so that n is effectively k+1, and then finish the construction with the first "k = n-1" method.

    For example, when n = 6 and k = 3, we will construct the array as [1, 2, 3, 6, 4, 5]. This consists of two parts: a construction of [1, 2] and a construction of [1, 4, 2, 3] where every element had 2 added to it (ie. [3, 6, 4, 5]).

    Algorithm

    As before, write [1, 2, ..., n-k-1] first. The remaining k+1 elements to be written are [n-k, n-k+1, ..., n], and we'll write them in alternating head and tail order.

    When we are writing the ith element from the remaining k+1, every even i is going to be chosen from the head, and will have value n-k + i//2. Every odd i is going to be chosen from the tail, and will have value n - i//2.

    Python

    class Solution(object):
        def constructArray(self, n, k):
            ans = list(range(1, n - k))
            for i in range(k+1):
                if i % 2 == 0:
                    ans.append(n-k + i//2)
                else:
                    ans.append(n - i//2)
    
            return ans
    

    Java

    class Solution {
        public int[] constructArray(int n, int k) {
            int[] ans = new int[n];
            int c = 0;
            for (int v = 1; v < n-k; v++) {
                ans[c++] = v;
            }
            for (int i = 0; i <= k; i++) {
                ans[c++] = (i%2 == 0) ? (n-k + i/2) : (n - i/2);
            }
            return ans;
        }
    }
    

    Complexity Analysis

    • Time Complexity: $$O(n)$$. We are making a list of size n.

    • Space Complexity: $$O(n)$$. Our answer is length n.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.