algoadvance

Given two integers n and k, you need to construct a list that contains integers from 1 to n such that the list has exactly k distinct integers like this. If several such lists exist, you may return any of them.

Example

Input: n = 3, k = 1
Output: [1, 2, 3]

Input: n = 3, k = 2
Output: [1, 3, 2] or [2, 3, 1]

Constraints:

• 1 <= k < n <= 10^4

Clarifying Questions

1. Can the same integer appear more than once in the list?
   • No, the integers must be unique and range from 1 to n.
2. What defines a distinct integer sequence in this context?
   • A sequence is considered to have k distinct integers if the absolute difference between consecutive elements in the sequence includes exactly k distinct values.
3. Are there any specific time constraints on the solution?
   • The solution should be efficient, ideally linear or near-linear time complexity.

Strategy

To solve this problem efficiently, we need a plan that ensures we use exactly k distinct absolute differences between consecutive elements. Here’s an effective strategy:

1. Forming Basic Structure:
   • We can start by constructing a sequence that inherently has k distinct absolute differences.
   • To achieve k distinct differences, use a combination of increasing and decreasing series.
2. Implementing the Plan:
   • Begin with an alternating sequence that guarantees k distinct differences:
     • Start with [1, n, 2, n-1, 3, n-2, …] until you reach k+1 elements.
   • Fill the rest of the sequence in a sorted manner to maintain the increasing order from k+1 difference onward.

Code

Here’s how to implement it in Python:

def constructArray(n, k):
    result = []
    left, right = 1, n
    while left <= right:
        if k > 1:
            if k % 2:
                result.append(left)
                left += 1
            else:
                result.append(right)
                right -= 1
            k -= 1
        else:
            result.extend(range(left, right + 1))
            break
    return result

# Example Usage:
n = 3
k = 2
print(constructArray(n, k))  # Output: [1, 3, 2] or any valid sequence

Time Complexity

• The time complexity of this algorithm is O(n) because we iterate through the range from 1 to n once.

• The space complexity is O(1) beyond the output list since we only use a few additional variables for tracking purposes.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?