667. Beautiful Arrangement II

MediumArrayMath
Leetcode Link

Problem Description

The problem provides us with two integers n and k. We are required to construct a list of n distinct positive integers, each ranging from 1 to n. The list needs to be such that the absolute differences between consecutive elements form a list that has exactly k distinct integers. This means that if we say our list is answer = [a1, a2, a3, ... , an], then the list formed by calculating the absolute differences |a1 - a2|, |a2 - a3|, |a3 - a4|, ..., |an-1 - an| should contain k unique values.

The task is to find any such list answer that satisfies these conditions and return it. This is an interesting problem as it mixes elements of combinatorics, construction, and the understanding of what patterns can emerge from the difference operations.

Intuition

To understand the solution approach, let's keep in mind what we're aiming for: distinct absolute differences. A key observation here is that the largest difference we can get is n - 1, which happens when you subtract 1 from n. To get k distinct differences, we can start by forming the sequence in such a way that it includes the largest differences first, which can be achieved by starting at 1, then jumping to n, then 2, and so on, alternating between the 'lows' and 'highs'.

For example, if n is 10 and k is 4, you would start with [1, 10, 2, 9...], because the differences are [9, 8, 7...] which covers 3 of the k distinct differences we need.

The provided solution alternates between the lowest and highest numbers not yet in the answer, which naturally creates the largest possible differences and starts to get smaller with each pair added to the list. Once we have created k differences, we continue the pattern in order to meet the list length n, but at this point, we no longer need to create new unique differences, just to maintain the pre-existing pattern.

Notice the alternating pattern in the for-loop where depending on the parity of i, we append either l (low end of unused numbers) or r (high end of unused numbers). The further for-loop picking up from k to n continues the pattern based on the last number added to ensure we finish with a pattern that still has only k unique differences.

Through this process, we're able to construct the desired list, satisfying the condition for k distinct differences, using a simple and efficient approach.

Learn more about Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

Solution Approach

The implementation provided in the reference solution uses a thoughtful pattern to satisfy the condition of k distinct differences. To walk you through it:

  1. The first for-loop iterates k times. During each iteration, it alternates between the lowest and highest numbers not yet added to ans. This is determined by checking the parity of i, the loop index. If it's even, we append and increment the l (the next smallest available integer) to ans. If it's odd, we append and decrement r (the next largest available integer) to ans. This loop effectively creates a "zig-zag" pattern in ans that guarantees the differences between adjacent numbers in ans have k distinct values.

  2. Once we have enough distinct differences, the objective of creating k distinct integers has been met, and we only need to fill the rest of ans with the remaining numbers in a way that doesn't create new distinct differences. This is done with the second for-loop which starts iterating from k up to n-1. The appending in this loop continues the established pattern based on the last number added to ans before this loop began.

    • If k is even, then the pattern must continue with the decreasing order, hence r is appended and decremented.
    • If k is odd, then the pattern must continue with increasing order, therefore l is appended and incremented.

By these steps, a valid ans with the right properties is constructed and ready to be returned as the solution.

Here is a high-level breakdown of the algorithm:

  • Initialize two pointers, l and r, to the smallest (1) and largest (n) numbers within the specified range respectively.

  • Alternate between appending l and r to ans, increasing l and decreasing r appropriately, until k distinct differences have been created.

  • Continue filling ans with the remaining numbers, ensuring the previously established pattern is maintained, until ans has a length of n.

  • Return ans as the final answer.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which two pointer techniques do you use to check if a string is a palindrome?

Example Walkthrough

Let's illustrate the solution approach with a small example. Let's use n = 5 and k = 3. We need to create a list of 5 distinct positive integers, each between 1 and 5, and the absolute differences of consecutive elements should have 3 distinct values.

  1. Initialize two pointers, l = 1 and r = 5 (smallest and largest numbers).

  2. Start the first for-loop to iterate k times. The goal here is to alternate between l and r to get distinct differences.

    • For the first iteration (i = 0 is even), append l to ans and increment l. ans = [1], l = 2, r remains 5.
    • For the second iteration (i = 1 is odd), append r to ans and decrement r. ans = [1, 5], l remains 2, r = 4.
    • For the third iteration (i = 2 is even), append l to ans and increment l. ans = [1, 5, 2], l = 3, r remains 4.

  3. Now, ans contains 1, 5, 2. The absolute differences so far are [4, 3]. We have our k = 3 distinct differences, because when we append the next number, it will either be a 3 or a 2, giving us the third difference (which would be 1), without creating a fourth difference.

  4. Determine the pattern to finish the last part of the list. We've placed 5 and 2, and k is odd, so we continue with this increasing pattern (because the last movement from 5 to 2 was a decrease).

    • Append l to ans and increment l. ans = [1, 5, 2, 3], l = 4, r remains 4.
    • At this point, appending l or r would get the same number (4 in this case), so we can just add the remaining number to the list.

  5. You finish with ans = [1, 5, 2, 3, 4]. The absolute differences of consecutive elements are [4, 3, 1, 1] which have three distinct values: 4, 3, and 1.

This example demonstrates how the pattern works by maximizing differences first and then following the pattern to fill the rest of the list without introducing new distinct differences. The final list ans = [1, 5, 2, 3, 4] satisfies the provided conditions.

Solution Implementation

1from typing import List
2
3class Solution:
4    def construct_array(self, n: int, k: int) -> List[int]:
5        # Initialize pointers for the smallest and largest elements
6        left, right = 1, n
7      
8        # This list will store our answer
9        result = []
10      
11        # First phase: creating k distinct differences
12        for i in range(k):
13            # If i is even, append from the left side (increasing numbers)
14            if i % 2 == 0:
15                result.append(left)
16                left += 1
17            # If i is odd, append from the right side (decreasing numbers)
18            else:
19                result.append(right)
20                right -= 1
21      
22        # Second phase: filling up the rest of the array
23        for i in range(k, n):
24            # If k is even, fill the rest of the array with decreasing numbers
25            if k % 2 == 0:
26                result.append(right)
27                right -= 1
28            # If k is odd, fill the rest of the array with increasing numbers
29            else:
30                result.append(left)
31                left += 1
32      
33        # Return the result array
34        return result
35
36# Example usage
37sol = Solution()
38print(sol.construct_array(10, 4))  # This will print an array of size 10 with exactly 4 distinct differences.
39
1class Solution {
2    public int[] constructArray(int n, int k) {
3        // Initialize left and right pointers to the start and end of the range
4        int left = 1, right = n;
5        // Create an array to store the result
6        int[] result = new int[n];
7      
8        // Fill the first part of the array with a 'k' difference pattern
9        for (int i = 0; i < k; ++i) {
10            // Alternate between the lowest and highest unused numbers
11            result[i] = (i % 2 == 0) ? left++ : right--;
12        }
13      
14        // Complete the rest of the array
15        for (int i = k; i < n; ++i) {
16            // If 'k' is even, decrement from right; otherwise, increment from left
17            // This ensures that the difference is no more than 'k'
18            result[i] = (k % 2 == 0) ? right-- : left++;
19        }
20      
21        // Return the constructed array
22        return result;
23    }
24}
25
1class Solution {
2public:
3    vector<int> constructArray(int n, int k) {
4        // 'left' and 'right' are used to keep track of the smallest and largest elements remaining
5        int left = 1, right = n;
6        vector<int> result(n); // This will be our final result array
7      
8        // The first part of the sequence should have 'k' distinct differences
9        for (int i = 0; i < k; ++i) {
10            // If 'i' is even, choose from the smallest values, else choose from the largest
11            result[i] = (i % 2 == 0) ? left++ : right--;
12        }
13      
14        // The remaining part of the sequence should be either increasing or decreasing
15        for (int i = k; i < n; ++i) {
16            // If 'k' is even, keep decreasing, else keep increasing.
17            // This keeps the absolute difference to 1, as required for elements after the initial 'k'
18            result[i] = (k % 2 == 0) ? right-- : left++;
19        }
20      
21        return result; // Return the final constructed array
22    }
23};
24
1// This function creates an array with a unique set of integers that have k different absolute
2// differences. The array is of length 'n', and the differences range between 1 and k.
3function constructArray(n: number, k: number): number[] {
4    let leftNumber = 1;       // Initialize the starting value for the low end
5    let rightNumber = n;      // Initialize the starting value for the high end
6    const answer = new Array<number>(n); // Initialize the answer array with length n
7
8    // Fill the first k elements of the array with the pattern to ensure k unique differences
9    for (let i = 0; i < k; ++i) {
10        // Alternate between the low and high end numbers to create the different differences
11        answer[i] = i % 2 === 0 ? leftNumber++ : rightNumber--;
12    }
13
14    // Fill the remaining elements of the array
15    // If k is even, continue decrementing from the rightNumber
16    // If k is odd, continue incrementing from the leftNumber
17    for (let i = k; i < n; ++i) {
18        answer[i] = k % 2 === 0 ? rightNumber-- : leftNumber++;
19    }
20
21    return answer; // Return the constructed array
22}
23
24// Example usage:
25// constructArray(10, 4) might return [1, 10, 2, 9, 3, 4, 5, 6, 7, 8] (k unique differences from 1 to 4)
26
Not Sure What to Study? Take the 2-min Quiz：

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

Time and Space Complexity

Time Complexity

The provided function consists of two for loops. The first loop runs k times, where k is a parameter. The second loop starts from k and runs until n. Therefore, the total number of operations is k + (n - k) = n, which means that every element from 1 to n is visited exactly once. This gives us a time complexity of O(n).

Space Complexity

The space complexity of the function is determined by the space required to store the output list, ans, which contains n elements since the function constructs an array of n unique integers. No additional data structures that grow with the input size are used. Thus, the space complexity of the function is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is the prefix sum of array [1, 2, 3, 4, 5]?

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫