Find two numbers summing to target without hashmap
Company: Meta
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Problem
Given an integer array `nums` (length `n`) and an integer `target`, return the **indices** `(i, j)` such that:
- `i != j`
- `nums[i] + nums[j] == target`
You may assume **exactly one** valid pair exists.
## Constraints
- `2 <= n <= 2 * 10^5`
- `-10^9 <= nums[k], target <= 10^9`
## Requirements
- Do **not** use a hash map / hash set solution.
- Aim to use sorting + two pointers.
- Output must be indices in the **original** array.
## Input/Output
- **Input:** `nums`, `target`
- **Output:** a pair of indices `[i, j]` (order does not matter)
## Example
- `nums = [2, 7, 11, 15]`, `target = 9` → output could be `[0, 1]`
Quick Answer: This question evaluates array manipulation, index-tracking, and algorithmic problem-solving skills, with emphasis on time and space complexity trade-offs when locating two elements that sum to a given target under input-size constraints.
Use sorting plus two pointers and return original indices for the unique pair; indices are sorted ascending.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([2,7,11,15], 9)
Expected Output: [0, 1]
Explanation: Prompt example.
Input: ([3,2,4], 6)
Expected Output: [1, 2]
Explanation: Middle pair.
Input: ([-1,-2,-3,-4,-5], -8)
Expected Output: [2, 4]
Explanation: Negative values.
Hints
- Use deterministic tie-breaking for prompts with multiple valid outputs.
- For design-style APIs, simulate operations with explicit inputs.