Find Positive Integer Solution for a Given Equation

medium two pointers monotonic function

Problem

You are given a callable function f(x, y) and a target z. The function is monotonically increasing: f(x, y) < f(x + 1, y) and f(x, y) < f(x, y + 1) for all x, y. With x and y drawn from 1 to 1000, return every positive integer pair [x, y] such that f(x, y) == z. Here we model f(x, y) = a·x + b·y so it can be evaluated in the browser.

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

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

All four pairs of positive integers sum to 5.

a (coef of x)

b (coef of y)

target z

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

var findSolution = function (customfunction, z) {
  const res = [];
  let x = 1, y = 1000;
  while (x <= 1000 && y >= 1) {
    const val = customfunction.f(x, y);
    if (val < z) {
      x++;
    } else if (val > z) {
      y--;
    } else {
      res.push([x, y]);
      x++;
      y--;
    }
  }
  return res;
};

class Solution {
    public List<List<Integer>> findSolution(CustomFunction cf, int z) {
        List<List<Integer>> res = new ArrayList<>();
        int x = 1, y = 1000;
        while (x <= 1000 && y >= 1) {
            int val = cf.f(x, y);
            if (val < z) {
                x++;
            } else if (val > z) {
                y--;
            } else {
                res.add(Arrays.asList(x, y));
                x++;
                y--;
            }
        }
        return res;
    }
}

vector<vector<int>> findSolution(CustomFunction& cf, int z) {
    vector<vector<int>> res;
    int x = 1, y = 1000;
    while (x <= 1000 && y >= 1) {
        int val = cf.f(x, y);
        if (val < z) {
            x++;
        } else if (val > z) {
            y--;
        } else {
            res.push_back({x, y});
            x++;
            y--;
        }
    }
    return res;
}

Explanation

The hidden function f(x, y) always grows when you increase x or y. That monotonic shape lets us find all pairs that equal z with two pointers instead of trying every combination.

Start at a corner: x = 1 (smallest) and y = 1000 (largest). Evaluate val = f(x, y) and compare it to the target z.

If val < z the result is too small, so we need a bigger value — increase x. If val > z it is too big, so decrease y. If val == z we found a pair: record [x, y], then move both pointers inward to look for the next one.

Example: f(x, y) = x + y, z = 5. From (1, 4) the sum is 5, record it and move to (2, 3) which is also 5, then (3, 2), then (4, 1). The answer is [[1,4],[2,3],[3,2],[4,1]].

Each step moves one pointer one way only, so the loop ends quickly in about x + y steps rather than scanning a full grid.

Time: O(x + y) Space: O(1)