LeetCode 1237 - Find Positive Integer Solution for a Given Equation

Difficulty: 🟡 Medium
Topics: Math, Two Pointers, Binary Search, Interactive

Solution

Problem Understanding

This problem gives us access to a hidden function f(x, y) through an interface. We are not allowed to know or implement the formula directly. Instead, we can only call the function with positive integers x and y and observe the result.

The important property is that the function is strictly increasing in both variables:

Increasing x while keeping y fixed always increases the output.
Increasing y while keeping x fixed always increases the output.

Our goal is to find every pair of positive integers (x, y) such that:

f(x, y) == z

The function implementations are hidden by the judge, but the monotonic property is guaranteed for all test cases.

The input consists of:

A callable CustomFunction object
An integer z

The output must be a list of all positive integer pairs [x, y] that satisfy the equation.

The constraints are small enough that brute force is technically possible:

1 <= z <= 100
All valid solutions are guaranteed to be within 1 <= x, y <= 1000

However, the problem is specifically designed to reward taking advantage of monotonic behavior. Since the function increases as either variable increases, we can eliminate large portions of the search space efficiently.

An important observation is that there may be:

Multiple valid pairs
No valid pairs
Only one valid pair

The output order does not matter.

Some edge cases that could cause issues in naive implementations include:

Functions that grow very quickly, such as multiplication or exponential-like behavior
Cases where only a single pair exists
Cases where no solution exists
Duplicate traversal of the same search space
Inefficient nested loops making unnecessary calls to the expensive hidden function

The monotonic guarantee is the key property that allows optimization.

Approaches

Brute Force Approach

The simplest approach is to try every possible pair (x, y) where both values range from 1 to 1000.

For every pair:

Call f(x, y)
Compare the result with z
If equal, store the pair

Because the constraints guarantee all valid answers lie within this range, brute force will always find every solution.

The main issue is efficiency. There are:

1000 * 1000 = 1,000,000

possible pairs.

That means up to one million calls to the hidden function. While this may still pass under current constraints, it ignores the most important property of the problem, monotonicity.

Key Insight

Since the function increases when either variable increases, we can use a two pointer strategy.

Suppose we start at:

x = 1
y = 1000

Now evaluate f(x, y).

If the result is too large, then increasing x would only make it larger, so we must decrease y.
If the result is too small, then decreasing y would only make it smaller, so we must increase x.
If the result equals z, we record the pair and move diagonally by increasing x and decreasing y.

This works exactly like searching a sorted matrix.

At every step, we eliminate either:

An entire row
Or an entire column

This reduces the total work to at most 2000 function calls.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(1000²) = O(1,000,000)	O(k)	Checks every possible pair
Optimal Two Pointers	O(1000)	O(k)	Uses monotonic property to eliminate rows and columns

Here, k represents the number of valid solutions.

Algorithm Walkthrough

Initialize two pointers:

x = 1
y = 1000

We begin at the top right corner of the conceptual search grid. 2. Create an empty result list. 3. While x <= 1000 and y >= 1:

Evaluate:

value = f(x, y)

If value == z:

Add [x, y] to the result list
Increase x
Decrease y

We move diagonally because:

Increasing x keeps future values larger
Decreasing y keeps future values smaller
Staying on the same row or column cannot produce the same value again due to strict monotonicity

If value < z:

Increase x.

Since the function increases with larger x, this is the only way to potentially reach z. 6. If value > z:

Decrease y.

Since the function increases with larger y, reducing y is the only way to reduce the result. 7. Continue until the pointers move out of bounds. 8. Return the collected result list.

Why it works

The algorithm works because the search space behaves like a sorted matrix.

At any position (x, y):

Everything below has larger values
Everything to the left has smaller values

Therefore:

If the current value is too large, all positions below are also too large
If the current value is too small, all positions to the left are also too small

Each move safely eliminates impossible regions without missing valid solutions.

Because the function is strictly increasing in both dimensions, no valid pair can be skipped.

Python Solution

from typing import List

"""
   This is the custom function interface.
   You should not implement it, or speculate about its implementation
   class CustomFunction:
       # Returns f(x, y) for any given positive integers x and y.
       # Note that f(x, y) is increasing with respect to both x and y.
       # i.e. f(x, y) < f(x + 1, y), f(x, y) < f(x, y + 1)
       def f(self, x, y):
  
"""

class Solution:
    def findSolution(self, customfunction: 'CustomFunction', z: int) -> List[List[int]]:
        result = []

        x = 1
        y = 1000

        while x <= 1000 and y >= 1:
            value = customfunction.f(x, y)

            if value == z:
                result.append([x, y])
                x += 1
                y -= 1
            elif value < z:
                x += 1
            else:
                y -= 1

        return result

The implementation follows the exact two pointer strategy described earlier.

We initialize x at the smallest possible value and y at the largest possible value. This positions us at the top right corner of the conceptual matrix.

Inside the loop, we evaluate the hidden function once per iteration.

When the value matches z, we record the pair and move diagonally. This prevents duplicate work because strict monotonicity guarantees no repeated values in the same row or column.

When the value is too small, we increase x because larger x produces larger function values.

When the value is too large, we decrease y because smaller y produces smaller function values.

The loop terminates once either pointer moves outside the valid range.

Go Solution

/**
 * This is the declaration of customFunction API.
 * @param  x    int
 * @param  y    int
 * @return      Returns f(x, y) for any given positive integers x and y.
 *              Note that f(x, y) is increasing with respect to both x and y.
 *              i.e. f(x, y) < f(x + 1, y), f(x, y) < f(x, y + 1)
 */

func findSolution(customFunction func(int, int) int, z int) [][]int {
    result := [][]int{}

    x := 1
    y := 1000

    for x <= 1000 && y >= 1 {
        value := customFunction(x, y)

        if value == z {
            result = append(result, []int{x, y})
            x++
            y--
        } else if value < z {
            x++
        } else {
            y--
        }
    }

    return result
}

The Go implementation mirrors the Python solution closely.

The result is stored as a slice of integer slices, [][]int.

Go does not require special overflow handling here because all values are guaranteed to fit inside a 32 bit signed integer, and Go's int type comfortably supports that range on LeetCode platforms.

Unlike Python lists, Go slices require explicit appending using append.

The loop logic and pointer movement are otherwise identical.

Worked Examples

Example 1

Input:

f(x, y) = x + y
z = 5

Initial state:

x = 1
y = 1000

Since values are far larger than 5, the algorithm keeps decreasing y.

Eventually:

x	y	f(x, y)	Action
1	4	5	Record [1,4], move diagonally
2	3	5	Record [2,3], move diagonally
3	2	5	Record [3,2], move diagonally
4	1	5	Record [4,1], move diagonally
5	0	Invalid	Stop

Final result:

[[1,4],[2,3],[3,2],[4,1]]

Example 2

Input:

f(x, y) = x * y
z = 5

Relevant iterations:

x	y	f(x, y)	Action
1	5	5	Record [1,5], move diagonally
2	4	8	Too large, decrease y
2	3	6	Too large, decrease y
2	2	4	Too small, increase x
3	2	6	Too large, decrease y
3	1	3	Too small, increase x
4	1	4	Too small, increase x
5	1	5	Record [5,1], move diagonally

Final result:

[[1,5],[5,1]]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1000)	Each iteration moves either x or y exactly once
Space	O(k)	Stores only the valid solution pairs

The important observation is that x only increases and y only decreases.

x can move at most 1000 times
y can move at most 1000 times

Therefore the total number of iterations is bounded by 2000, which simplifies to O(1000).

The algorithm is dramatically more efficient than brute force because it never revisits any state.

Test Cases

from typing import List

class CustomFunction:
    def f(self, x: int, y: int) -> int:
        pass

class AddFunction(CustomFunction):
    def f(self, x: int, y: int) -> int:
        return x + y

class MultiplyFunction(CustomFunction):
    def f(self, x: int, y: int) -> int:
        return x * y

class QuadraticFunction(CustomFunction):
    def f(self, x: int, y: int) -> int:
        return x * x + y * y

solution = Solution()

# Example 1: addition function
assert solution.findSolution(AddFunction(), 5) == [
    [1, 4],
    [2, 3],
    [3, 2],
    [4, 1]
]

# Example 2: multiplication function
assert solution.findSolution(MultiplyFunction(), 5) == [
    [1, 5],
    [5, 1]
]

# Single valid pair
assert solution.findSolution(AddFunction(), 2) == [
    [1, 1]
]

# No valid solution
assert solution.findSolution(QuadraticFunction(), 3) == []

# Multiple sparse solutions
assert solution.findSolution(QuadraticFunction(), 25) == [
    [3, 4],
    [4, 3]
]

# Smallest possible z
assert solution.findSolution(MultiplyFunction(), 1) == [
    [1, 1]
]

# Larger target value
assert solution.findSolution(AddFunction(), 100) == [
    [1, 99],
    [2, 98],
    [3, 97],
    [4, 96],
    [5, 95],
    [6, 94],
    [7, 93],
    [8, 92],
    [9, 91],
    [10, 90],
    [11, 89],
    [12, 88],
    [13, 87],
    [14, 86],
    [15, 85],
    [16, 84],
    [17, 83],
    [18, 82],
    [19, 81],
    [20, 80],
    [21, 79],
    [22, 78],
    [23, 77],
    [24, 76],
    [25, 75],
    [26, 74],
    [27, 73],
    [28, 72],
    [29, 71],
    [30, 70],
    [31, 69],
    [32, 68],
    [33, 67],
    [34, 66],
    [35, 65],
    [36, 64],
    [37, 63],
    [38, 62],
    [39, 61],
    [40, 60],
    [41, 59],
    [42, 58],
    [43, 57],
    [44, 56],
    [45, 55],
    [46, 54],
    [47, 53],
    [48, 52],
    [49, 51],
    [50, 50],
    [51, 49],
    [52, 48],
    [53, 47],
    [54, 46],
    [55, 45],
    [56, 44],
    [57, 43],
    [58, 42],
    [59, 41],
    [60, 40],
    [61, 39],
    [62, 38],
    [63, 37],
    [64, 36],
    [65, 35],
    [66, 34],
    [67, 33],
    [68, 32],
    [69, 31],
    [70, 30],
    [71, 29],
    [72, 28],
    [73, 27],
    [74, 26],
    [75, 25],
    [76, 24],
    [77, 23],
    [78, 22],
    [79, 21],
    [80, 20],
    [81, 19],
    [82, 18],
    [83, 17],
    [84, 16],
    [85, 15],
    [86, 14],
    [87, 13],
    [88, 12],
    [89, 11],
    [90, 10],
    [91, 9],
    [92, 8],
    [93, 7],
    [94, 6],
    [95, 5],
    [96, 4],
    [97, 3],
    [98, 2],
    [99, 1]
]

Test Summary

Test	Why
Addition function with z=5	Verifies multiple valid pairs
Multiplication function with z=5	Verifies sparse solutions
Addition with z=2	Tests smallest nontrivial solution
Quadratic with z=3	Tests no solution case
Quadratic with z=25	Tests nonconsecutive valid pairs
Multiplication with z=1	Tests minimum boundary
Addition with z=100	Tests many valid solutions

Edge Cases

No Valid Pairs Exist

Some functions and target values produce no valid solution. For example:

f(x, y) = x² + y²
z = 3

There are no positive integers whose squares sum to 3.

A buggy implementation might loop incorrectly or accidentally return invalid pairs. Our implementation safely terminates because one pointer moves during every iteration, guaranteeing progress.

Only One Valid Pair Exists

For cases like:

f(x, y) = x * y
z = 1

The only valid pair is [1,1].

Some implementations accidentally skip the solution when moving pointers after a match. Our solution records the pair before updating both pointers, ensuring no solution is lost.

Large Regions of Invalid Values

When y starts at 1000, many function values may initially be far larger than z.

A naive solution would still check every pair individually. The two pointer method efficiently eliminates entire columns by repeatedly decreasing y until the search region becomes relevant.

This is the key optimization that makes the algorithm efficient.