algoadvance

Leetcode 667. Beautiful Arrangement II

Problem Statement

Given two integers n and k, you need to construct a permutation of the integers from 1 to n such that there are exactly k distinct absolute differences between consecutive elements.

Clarifying Questions

  1. Constraints:
    • Is it guaranteed that a valid permutation exists for any n and k satisfying 1 ≤ k < n?
      • Yes, it’s guaranteed by the problem statement.
    • Can n be a large value like 10^6, and what is the expected complexity?
      • The constraints typically imply that n can be large, but an efficient solution is expected to handle this.
  2. Output Format:
    • The function should return a list of integers representing the permutation.
    • Is there a specific format required for the output permutation, or any permutation with k distinct differences is acceptable?
      • Any permutation that satisfies the condition is acceptable.

Strategy

  1. Initial Thoughts:
    • We need a permutation such that exactly k distinct absolute differences exist.
    • We can start with a simple increasing permutation from 1 to n.
  2. Key Insight:
    • The idea is to construct the permutation in such a way that the differences are controlled.
    • An effective strategy is to alternate between the smallest and largest remaining elements to ensure distinct differences initially, and then continue with a simple increase.
  3. Construction Plan:
    • Start from the smallest and largest remaining numbers.
    • Alternate between the smallest (left) and largest (right) until we create k distinct differences.
    • After achieving k distinct differences, fill the remaining part of the permutation straightforwardly.

Code

Let’s implement this strategy in the code:

import java.util.*;

public class BeautifulArrangementII {
    public int[] constructArray(int n, int k) {
        int[] result = new int[n];
        int left = 1, right = n;
        boolean flag = true;
        
        for (int i = 0; i < k; i++) {
            if (flag) {
                result[i] = left++;
            } else {
                result[i] = right--;
            }
            flag = !flag;
        }
        
        if (k % 2 == 0) {
            for (int i = k; i < n; i++) {
                result[i] = left++;
            }
        } else {
            for (int i = k; i < n; i++) {
                result[i] = right--;
            }
        }
        
        return result;
    }
    
    public static void main(String[] args) {
        BeautifulArrangementII solution = new BeautifulArrangementII();
        System.out.println(Arrays.toString(solution.constructArray(3, 1))); // [1, 2, 3]
        System.out.println(Arrays.toString(solution.constructArray(3, 2))); // [1, 3, 2] or [2, 1, 3] etc.
    }
}

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI