Find Positive Integer Solution: Two-Pointer Search Pattern

LeetCode 1237, Find Positive Integer Solution for a Given Equation, asks you to find all pairs (x, y) of positive integers such that f(x, y) == z, where f is a hidden function that is monotonically increasing in both x and y. You cannot see the function's code. You can only call f(x, y) and observe the result. The twist is that the monotonicity gives you enough structure to search efficiently without brute-forcing every possible pair.

Why this problem matters

This problem isolates a pattern you will see in many two-pointer and binary-search problems: exploiting monotonicity to eliminate large chunks of the search space in a single step. Sorted arrays, matrices with row and column ordering, and custom comparator functions all share this property. If you can recognize when a function is monotonically increasing in two independent variables, you can apply the same two-pointer sweep to cut the search from O(n^2) down to O(n).

The key insight

Because f is monotonically increasing in both x and y, the value grid has a specific shape. In any row, values increase left to right. In any column, values increase top to bottom. This means you can start at one corner of the grid and walk diagonally toward the solutions.

Start with x = 1 and y = 1000 (the maximum). Compare f(x, y) to z:

• If f(x, y) == z, you found a solution. Record it, then move both pointers (increment x, decrement y).
• If f(x, y) < z, the value is too small. Increasing x will make f larger, so increment x.
• If f(x, y) > z, the value is too large. Decreasing y will make f smaller, so decrement y.

Each step either increments x or decrements y (or both). Since x only goes up and y only goes down, the algorithm terminates after at most x_max + y_max steps.

The solution

def findSolution(customfunction, z):
    results = []
    x, y = 1, 1000
    while x <= 1000 and y >= 1:
        val = customfunction.f(x, y)
        if val == z:
            results.append([x, y])
            x += 1
            y -= 1
        elif val < z:
            x += 1
        else:
            y -= 1
    return results

The function starts x at 1 (the smallest positive integer) and y at 1000 (the upper bound given by the constraints). On each iteration, it evaluates f(x, y) and decides which pointer to move based on the comparison with z.

When f(x, y) equals z, both pointers move because no other pair sharing the same x or the same y can also produce z. If another y' > y existed with f(x, y') == z, that would contradict monotonicity since f(x, y') > f(x, y) == z. The same logic applies in the other direction.

Visual walkthrough

Here is the algorithm running on f(x, y) = x * y with z = 6. The orange arrow marks the current x row and the green arrow marks the current y column.

The algorithm found both solutions, (2, 3) and (3, 2), in five steps. It never had to check all 16 cells in the grid. The monotonicity of f let it skip entire rows and columns after each comparison.

Complexity analysis

Time: each step increments x or decrements y (or both). Since x starts at 1 and goes up to at most 1000, and y starts at 1000 and goes down to at most 1, the total number of steps is at most 1999. That makes the time complexity O(x_max + y_max), which simplifies to O(n) where n is the range of valid values.

Space: the algorithm uses a constant number of variables (not counting the output list). The output itself is at most O(min(x_max, y_max)) pairs, but the working space is O(1).

The building blocks

1. Monotonic function search

The core idea is that a monotonically increasing function lets you binary-search or two-pointer walk to the target. If you know that making one variable larger always increases the output, you can confidently move in one direction without missing anything.

while x <= upper and y >= 1:
    val = f(x, y)
    if val == target:
        record(x, y)
        x += 1
        y -= 1
    elif val < target:
        x += 1
    else:
        y -= 1

This template works for any monotonically increasing function of two variables. The specific function does not matter.

2. Corner-start elimination

Starting at the top-right (or bottom-left) corner of the search space gives you maximum information per step. At the top-right corner, one variable is at its minimum and the other at its maximum. This means you always have one direction that increases f and one that decreases it, which lets every comparison eliminate a row or column.

x, y = 1, max_y

If you started at the top-left corner (both minimums), both directions would increase f, and you would not know which way to go when f(x, y) < z. The corner choice matters.

Edge cases

• No solutions exist: the while loop finishes without finding any matches. The function returns an empty list, which is correct.
• All pairs in a row are solutions: this cannot happen for a monotonically increasing function with distinct outputs for distinct inputs. But if f is constant along a row (not strictly increasing), the problem constraints guarantee it is monotonically increasing, so each row has at most one matching y.
• z is very small or very large: when z = 1, only f(1, 1) might match. When z is larger than f(1000, 1000), nothing matches. The algorithm handles both naturally because the pointers quickly go out of bounds.
• Upper bound of 1000: the constraint says 1 <= x, y <= 1000. Starting y at 1000 covers the full range.

From understanding to recall

Reading through this solution, the logic feels simple. Start at a corner, compare, move the right pointer. But reproducing it under pressure is a different story. The tricky part is remembering why the corner start works, why both pointers move on a match, and why no solutions get skipped.

These details slip away fast if you only read them once. The building blocks here (monotonic function search and corner-start elimination) are small and self-contained. They are perfect candidates for spaced repetition. Drill them a few times over the course of two weeks, and the reasoning becomes automatic.

Once these building blocks are in long-term memory, you can assemble the solution for this problem and for related problems like Search a 2D Matrix II without re-deriving the logic from scratch.

Related posts

• Two Sum II - Input Array Is Sorted - The classic converging two-pointer problem on a sorted array
• Container With Most Water - Another two-pointer problem where monotonicity drives the pointer movement
• Binary Search - The foundation of searching in monotonic structures

If you want to lock in the monotonic search and corner-start elimination building blocks so they are available on demand during interviews, CodeBricks breaks them down into focused drills that adapt to your memory.