algoadvance

Leetcode 667. Beautiful Arrangement II

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 exactly k different integers exist such that there are exactly k distinct absolute differences between consecutive elements of the list.

Return the list. If there are multiple valid lists, you can return any of them.

Clarifying Questions

  1. Can n be less than 0?
    • No, n is a positive integer by the constraints.
  2. What are the ranges for n and k?
    • Typically, in such problems, n can be quite large (up to 10,000). k is such that 1 <= k < n.

Code

#include <vector>
#include <iostream>
#include <cmath>

std::vector<int> constructArray(int n, int k) {
    std::vector<int> result;
    int low = 1, high = n;
    for (int i = 0; i <= k; ++i) {
        if (i % 2 == 0) {
            result.push_back(low++);
        } else {
            result.push_back(high--);
        }
    }
    if (k % 2 == 0) {
        for (int i = high; i >= low; --i) {
            result.push_back(i);
        }
    } else {
        for (int i = low; i <= high; ++i) {
            result.push_back(i);
        }
    }
    return result;
}

int main() {
    int n = 10, k = 4;
    std::vector<int> result = constructArray(n, k);
    for (int num : result) {
        std::cout << num << " ";
    }
    return 0;
}

Strategy

  1. Initialization:
    • Begin with two pointers: low = 1 and high = n.
    • This approach interleaves the smallest and the largest remaining numbers.
  2. First Part (Handling k unique differences):
    • For the first k+1 elements, alternate between picking the smallest available number (low) and the largest available number (high). This guarantees that we achieve k unique differences.
  3. Second Part (Filling the remaining n - k - 1 elements):
    • Depending on whether k is odd or even, fill the remaining part of the array:
      • If k is odd, continue with the numbers in the increasing order.
      • If k is even, continue with the numbers in the decreasing order.

This strategy ensures that exactly k unique differences are achieved because the alternating selections in the first part create diverse gaps that cannot repeat within the initial k+1 numbers.

Time Complexity

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