Abstract / Summary

Given two integers n and k, create an array of length n where exactly k pairs of adjacent elements are coprime.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 61% (100k+ submissions).

Typical patterns to solve this problem:

• Array
• Math

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a class Solution with a method constructArray that produces a sequence of integers from 1 to n. The sequence is generated on-the-fly using a Python generator (yield). The algorithm is designed to create exactly k distinct absolute differences between consecutive elements, a requirement often seen in combinatorial construction problems. By alternating the direction of traversal for the first k-1 steps and then proceeding monotonically, the method guarantees the desired difference pattern while using minimal auxiliary storage.

Core Logic

The method begins by initializing a small helper list named next. This list holds the next candidate value for each traversal direction. Index 1 corresponds to the forward direction (incrementing values), while index 2 corresponds to the backward direction (decrementing values). The initial values are set to the smallest and largest numbers in the target range, respectively.

next = [ None, 1, n ]

A variable dir is introduced to indicate the current direction of movement. It starts with a positive value (+1) meaning the forward direction.

dir  = +1

The main loop iterates exactly n times, matching the length of the desired output. In each iteration the algorithm yields the current element, updates the stored next value for the active direction, and possibly flips the direction for the next step.

for i in range(n):
    yield next[dir]
    next[dir] +=  dir
    if i + 1 < k:          # alternate direction
        dir    = -dir

Yielding the Current Element

The statement yield next[dir] returns the element that belongs to the current position in the output sequence. Because the method is a generator, the caller can consume the values lazily, which is useful when only a portion of the sequence is needed or when the sequence is large.

Updating the Next Candidate

After yielding, the algorithm increments (or decrements) the stored next value for the active direction by adding dir. Since dir is either +1 or -1, this operation moves the pointer one step forward or backward in the numeric range.

next[dir] +=  dir

Direction Alternation

The conditional if i + 1 < k: controls when the direction should be reversed. For the first k-1 iterations (i ranging from 0 to k-2), the direction flips after each element, creating a pattern that yields large differences (alternating between the low and high ends of the range). Once i + 1 reaches k, the condition fails and the direction remains fixed, producing a monotonic tail of consecutive numbers that generate a difference of 1.

if i + 1 < k:          # alternate direction
    dir    = -dir

Edge Cases Handled

When k equals 1, the condition i + 1 < k is never satisfied, so the direction never flips. The generator therefore produces a simple increasing sequence 1, 2, …, n, which naturally has only one distinct difference (the value 1).

When k equals n, the direction flips on every iteration up to the last element. This creates an alternating high-low pattern such as 1, n, 2, n-1, …, ensuring that each adjacent pair contributes a unique difference until the final monotonic segment is reached.

If k is any intermediate value, the algorithm correctly alternates for the first k-1 steps and then settles into a steady increase, guaranteeing exactly k distinct differences regardless of the specific values of n and k within their valid ranges.

Performance Optimizations

The implementation achieves constant extra space by storing only three integer values (next[1], next[2], and dir). No auxiliary arrays proportional to n are allocated, which keeps memory usage minimal even for large inputs.

Using a generator (yield) avoids constructing the entire result list in memory. Consumers can iterate over the output directly, benefiting from lazy evaluation and reduced peak memory consumption.

The arithmetic updates (next[dir] += dir) are simple integer operations with O(1) cost per iteration, and the direction flip is a single sign change. This tight loop minimizes overhead and makes the method well-suited for performance-critical contexts where many calls are made with large n.

Imagine a row of numbers from one to ten, like stations on a train track. This code is like a game of hopping back and forth along those stations to make sure the gap between each step changes in a special way.

At the start, the game sets up two pointers. One pointer stays at the very beginning of the track, and the other pointer sits at the very end.

The code looks at the value k, which is the number of different-sized jumps it needs to make. To get these different hops, it starts by taking a huge jump from the beginning to the end. Then, it turns around and takes another jump from the end toward the beginning. It keeps swapping which pointer it uses to jump, which makes the distance between the spots get smaller with every hop.

Once it has made enough of those interesting, changing jumps, it finishes the rest of the path by just taking tiny, single steps forward one by one until it reaches the end of the track. By the time it finishes, it has visited every single station exactly once, but the space between each stop creates a neat pattern of different gaps.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java					TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java			Go		TS
	LeetcodeHelp	C++	Python		Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python		Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis			JS
	halfrost							Go
	JoshCrozier			JS
	lkwq007		Python
	ruoru					Rust
	suxrobGM								C#
	trung-hn		Python
	vthwang				Java
	wisdompeak	C++
	yuanliu666						Kotlin
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
halfrost	Go
JoshCrozier	JavaScript
lkwq007	Python
ruoru	Rust
suxrobGM	C#
trung-hn	Python
vthwang	Java
wisdompeak	C++
yuanliu666	Kotlin
YuriSpiridonov	Python
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality