LeetCode 1387 - Sort Integers by The Power Value

LeetCode Problem 1387

Difficulty: 🟡 Medium
Topics: Dynamic Programming, Memoization, Sorting

Solution

Problem Understanding

This problem asks us to rank integers according to a special metric called the "power value". The power value of a number is determined by repeatedly applying the Collatz transformation rules until the number becomes 1.

The rules are:

• If the number is even, divide it by 2
• If the number is odd, replace it with 3 * x + 1

The power value is simply the number of transformations required to reach 1.

For example:

• 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1
• This sequence contains 7 transitions, so the power value of 3 is 7

The input consists of three integers:

• lo, the lower bound of the interval
• hi, the upper bound of the interval
• k, the position we want after sorting

We must consider every integer in the range [lo, hi], compute its power value, then sort the numbers according to two rules:

1. Smaller power value comes first
2. If two numbers have the same power value, the smaller number comes first

After sorting, we return the kth number in the sorted order.

The constraints are relatively small:

• 1 <= lo <= hi <= 1000
• At most 1000 numbers exist in the range

This tells us that we do not need extremely advanced optimization techniques. However, repeatedly recomputing Collatz sequences for many overlapping values can still be inefficient. Many numbers in different sequences eventually converge to the same intermediate values, so memoization becomes a natural optimization.

An important guarantee is that every number in the range will eventually reach 1. This avoids infinite loops and ensures the power computation always terminates.

Several edge cases are important:

• A range containing only one number
• Multiple numbers sharing the same power value
• Very small numbers such as 1
• Large Collatz chains where intermediate values become much larger than 1000

The last point is especially important because although the input range is small, Collatz sequences may temporarily grow far beyond the original interval.

Approaches

Brute Force Approach

The most direct solution is to compute the power value independently for every number in the interval.

For each integer x in [lo, hi]:

1. Simulate the Collatz process step by step
2. Count how many operations are needed to reach 1
3. Store (power_value, number) pairs
4. Sort the list
5. Return the kth number

This approach is correct because it explicitly computes the exact power value for every number and sorts according to the problem rules.

However, it performs a large amount of repeated work. Different sequences often overlap heavily. For example:

• 12 → 6 → 3 → 10 → ...
• 13 → 40 → 20 → 10 → ...

Both sequences eventually reach 10, meaning the remaining computations are duplicated.

Without caching, the same power values may be recomputed many times.

Optimal Approach, Memoization with Sorting

The key observation is that Collatz sequences overlap extensively.

If we already know the power value of some number y, then the power value of another number x that transitions into y can be computed immediately:

• power(x) = 1 + power(y)

This naturally suggests memoization.

We use a hash map to cache previously computed power values. Whenever we encounter a number whose power value is already known, we stop recursion and reuse the cached result.

This dramatically reduces redundant computation because each intermediate number is processed only once.

After computing all power values with memoization, we sort the interval and return the kth element.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × m)	O(n)	Recomputes many Collatz chains repeatedly
Optimal	O(n log n + U)	O(U)	Uses memoization to avoid repeated calculations

Here:

• n = hi - lo + 1
• m is the average Collatz sequence length
• U is the number of unique intermediate values encountered

Algorithm Walkthrough

Step 1: Create a Memoization Map

We initialize a hash map storing already computed power values.

We begin with:

memo = {1: 0}

This means the power value of 1 is 0 because it already equals 1.

This memoization map allows us to reuse previous computations efficiently.

Step 2: Define a Recursive Power Function

We create a recursive function power(x).

The function works as follows:

1. If x already exists in the memo map, return the cached value
2. Otherwise:

• If x is even, recursively compute power(x // 2)
• If x is odd, recursively compute power(3 * x + 1)

3. Add 1 to represent the current transformation
4. Store the result in the memo map
5. Return the computed value

This recursive structure mirrors the exact definition of the Collatz process.

Step 3: Build the Array of Numbers

We generate all integers from lo to hi.

For each number, we compute its power value using the memoized function.

Step 4: Sort the Numbers

We sort using a custom sorting key:

key = (power_value, number)

This guarantees:

• Smaller power values appear first
• Ties are broken by the integer value itself

Step 5: Return the kth Element

Since indexing is zero based, the answer is:

numbers[k - 1]

Why it works

The algorithm works because the recursive function exactly follows the Collatz transformation rules defined in the problem. Memoization does not change correctness, it only avoids recomputation.

The sorting step uses the precise ordering required by the problem statement:

1. Primary key, power value
2. Secondary key, integer value

Therefore, the resulting order is guaranteed to match the required sorted order, and selecting the kth element returns the correct answer.

Python Solution

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        memo = {1: 0}

        def power(x: int) -> int:
            if x in memo:
                return memo[x]

            if x % 2 == 0:
                memo[x] = 1 + power(x // 2)
            else:
                memo[x] = 1 + power(3 * x + 1)

            return memo[x]

        numbers = list(range(lo, hi + 1))

        numbers.sort(key=lambda num: (power(num), num))

        return numbers[k - 1]

The implementation begins by initializing the memoization dictionary with the base case 1: 0.

The nested power() function recursively computes the power value for any integer. Before doing any work, it checks whether the value already exists in the cache. If so, it immediately returns the stored answer.

If the number is even, the function recursively computes the power value of x // 2. If odd, it computes the power value of 3 * x + 1. In both cases, 1 is added for the current transformation step.

After computing all power values, the code generates the interval [lo, hi] and sorts it using a tuple sorting key:

(power(num), num)

Python tuple comparison automatically handles the tie breaking rule correctly.

Finally, the code returns the k - 1 indexed element because Python lists use zero based indexing.

Go Solution

package main

import "sort"

func getKth(lo int, hi int, k int) int {
	memo := map[int]int{
		1: 0,
	}

	var power func(int) int

	power = func(x int) int {
		if val, exists := memo[x]; exists {
			return val
		}

		if x%2 == 0 {
			memo[x] = 1 + power(x/2)
		} else {
			memo[x] = 1 + power(3*x+1)
		}

		return memo[x]
	}

	numbers := make([]int, 0)

	for i := lo; i <= hi; i++ {
		numbers = append(numbers, i)
	}

	sort.Slice(numbers, func(i, j int) bool {
		pi := power(numbers[i])
		pj := power(numbers[j])

		if pi == pj {
			return numbers[i] < numbers[j]
		}

		return pi < pj
	})

	return numbers[k-1]
}

The Go implementation follows the same algorithmic structure as the Python version.

A map[int]int is used for memoization. Go does not support nested named functions directly, so the recursive function is declared using a function variable:

var power func(int) int

Sorting is implemented using sort.Slice with a custom comparator.

Unlike Python tuple comparison, Go requires explicit comparison logic for tie handling.

Go integers are large enough for the problem constraints, so integer overflow is not a concern here.

Worked Examples

Example 1

Input:

lo = 12, hi = 15, k = 2

We compute power values for each number.

Number	Sequence Length	Power Value
12	12 → 6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1	9
13	13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1	9
14	14 → 7 → 22 → 11 → 34 → 17 → ... → 1	17
15	15 → 46 → 23 → 70 → ... → 1	17

Now we sort by:

(power, number)

Sorted order:

Number	Power
12	9
13	9
14	17
15	17

The second element is:

13

Output:

13

Example 2

Input:

lo = 7, hi = 11, k = 4

Power values:

Number	Power
7	16
8	3
9	19
10	6
11	14

Sorting gives:

Position	Number	Power
1	8	3
2	10	6
3	11	14
4	7	16
5	9	19

The fourth element is:

7

Output:

7

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n + U)	Sorting costs O(n log n), memoized power computations process each unique value once
Space	O(U)	Memoization stores computed power values

Here:

• n = hi - lo + 1
• U is the number of unique intermediate Collatz values encountered

The dominant cost is sorting the interval. Memoization ensures that repeated Collatz computations are avoided, significantly reducing redundant work.

Test Cases

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        memo = {1: 0}

        def power(x: int) -> int:
            if x in memo:
                return memo[x]

            if x % 2 == 0:
                memo[x] = 1 + power(x // 2)
            else:
                memo[x] = 1 + power(3 * x + 1)

            return memo[x]

        numbers = list(range(lo, hi + 1))
        numbers.sort(key=lambda num: (power(num), num))

        return numbers[k - 1]

solution = Solution()

assert solution.getKth(12, 15, 2) == 13  # provided example 1
assert solution.getKth(7, 11, 4) == 7    # provided example 2

assert solution.getKth(1, 1, 1) == 1     # single element range
assert solution.getKth(1, 2, 1) == 1     # smallest k
assert solution.getKth(1, 2, 2) == 2     # largest k in small range

assert solution.getKth(10, 20, 5) == 13  # medium range test
assert solution.getKth(5, 5, 1) == 5     # identical lo and hi

assert solution.getKth(20, 30, 1) == 20  # smallest power in range
assert solution.getKth(20, 30, 11) == 27 # largest k in range

assert solution.getKth(1, 1000, 777) >= 1  # stress test over full constraints

Test	Why
(12, 15, 2)	Validates provided example with tie breaking
(7, 11, 4)	Validates provided example with varied powers
(1, 1, 1)	Tests smallest possible input
(1, 2, 1)	Tests smallest k
(1, 2, 2)	Tests largest valid k
(10, 20, 5)	Verifies general correctness on medium range
(5, 5, 1)	Tests single number interval
(20, 30, 1)	Ensures sorting works correctly
(20, 30, 11)	Ensures final element retrieval works
(1, 1000, 777)	Stress test for upper constraints

Edge Cases

One important edge case occurs when the interval contains only a single number. For example:

lo = hi = 5

In this case, no actual sorting is needed because only one element exists. A buggy implementation might incorrectly assume multiple elements are always present. The current implementation handles this naturally because the generated list contains exactly one value and sorting a single element list is valid.

Another important edge case involves ties in power values. For example:

12 and 13 both have power value 9

If the implementation sorts only by power value, the relative order may become inconsistent depending on the sorting algorithm. The problem explicitly requires ties to be broken by the numeric value itself. The implementation solves this using:

(power(num), num)

This guarantees stable and correct ordering.

A third important edge case is that intermediate Collatz values can become much larger than the original range. Even though inputs are at most 1000, sequences may temporarily grow into much larger numbers. A naive solution that assumes all values remain within the original range could fail or allocate insufficient storage. The memoization dictionary dynamically stores any encountered integer, so the implementation handles large intermediate values correctly without assumptions about their size.