Beautiful Arrangement II Solution in Java

Problem Description

The “Beautiful Arrangement II” problem on LeetCode is about arranging `n` distinct integers from `1` to `n` such that the absolute difference between any two consecutive integers is either `k` or `k-1`. Imagine hosting a party and wanting to seat your friends in a way that avoids arguments over the last slice of pizza. You need to ensure the distance between their personalities (or numbers) is just right.

Code Solution

Copy Code

class Solution {
  public int[] constructArray(int n, int k) {
    int[] ans = new int[n];

    for (int i = 0; i < n - k; ++i)
      ans[i] = i + 1;

    for (int i = 0; i < k; ++i) {
      if (i % 2 == 0)
        ans[n - k + i] = n - i / 2;
      else
        ans[n - k + i] = n - k + (i + 1) / 2;
    }

    return ans;
  }
}

Approach

The approach is straightforward. First, we fill the initial part of the array with the first `n-k` integers. Then, we fill the remaining `k` positions by alternating between the largest and smallest available numbers. This ensures that the absolute differences between consecutive numbers meet the required conditions. It’s like playing a game of hopscotch, but instead of chalk, you’re using numbers!

Time and Space Complexity

• Time Complexity: O(n) - We iterate through the array a couple of times, which is linear in relation to `n`.
• Space Complexity: O(n) - We use an additional array of size `n` to store the result.

Real-World Example

Think of it like organizing a dance floor at a wedding. You want to ensure that the bride and groom (the largest numbers) are not too far apart from their friends (the smaller numbers). You want to create a beautiful arrangement where everyone can dance without stepping on each other's toes.