function twoSumBrute(numbers, target) {
const n = numbers.length;
for (let i = 0; i < n - 1; i++) {
for (let j = i + 1; j < n; j++) {
if (numbers[i] + numbers[j] === target) {
return [i + 1, j + 1];
}
}
}
return [];
}
if (typeof require !== 'undefined' && require.main === module) {
console.log('Brute-force Two Sum II tests');
console.log(twoSumBrute([2,7,11,15], 9));
console.log(twoSumBrute([2,3,4], 6));
console.log(twoSumBrute([-1,0], -1));
}
// File: javascript.brute.js
// Problem: Two Sum II - Input array is sorted (LeetCode 167)
// Approach: Brute-force nested loops (O(n^2))
// Expected: return 1-indexed positions [i+1, j+1]
// Time: O(n^2), Space: O(1)
/**
* Brute-force solution for Two Sum II (sorted array).
* Tries every pair (i, j) with i < j and returns the first matching indices in 1-based format.
* This implementation is useful as a clear baseline to explain correctness in interviews.
*
* @param {number[]} numbers - sorted array of integers (ascending)
* @param {number} target - target sum
* @returns {[number, number]} pair of 1-indexed positions or [] if none
*/
function twoSumBrute(numbers, target) {
const n = numbers.length;
for (let i = 0; i < n - 1; i++) {
// Early micro-optimization: if current number already exceeds target and all numbers positive,
// you could break here. But since array can include negatives, we keep the full check.
for (let j = i + 1; j < n; j++) {
if (numbers[i] + numbers[j] === target) {
// Return 1-indexed positions as required by LeetCode 167
return [i + 1, j + 1];
}
}
}
return []; // If no pair found (LeetCode guarantees one solution unless variant differs)
}
// Simple runner & tests for local execution. When running with node, this block helps quick verification.
if (typeof require !== 'undefined' && require.main === module) {
console.log('Brute-force Two Sum II tests');
console.log(twoSumBrute([2,7,11,15], 9)); // [1,2]
console.log(twoSumBrute([2,3,4], 6)); // [1,3]
console.log(twoSumBrute([-1,0], -1)); // [1,2]
}
/*
COMMENTS — Brute (Two Sum II)
Why this solution:
- Simple and explicit: demonstrates correctness by exhaustive search.
- Good for whiteboard explanation to show baseline before optimizing.
Where to present in interview:
- Start with this to show you can reason about correctness, then explain optimized approach.
Micro-notes & trade-offs:
- Works on sorted input but doesn't exploit sorting.
- If numbers are all positive and numbers[i] > target, you could early-break inner/outer loops.
- Complexity is quadratic: O(n^2) time, O(1) extra space.
*/
function twoSumOptimized(numbers, target) {
let left = 0;
let right = numbers.length - 1;
while (left < right) {
const sum = numbers[left] + numbers[right];
if (sum === target) {
return [left + 1, right + 1];
}
if (sum < target) {
left++;
} else {
right--;
}
}
return [];
}
if (typeof require !== 'undefined' && require.main === module) {
console.log('\nOptimized Two Sum II tests');
console.log(twoSumOptimized([2,7,11,15], 9));
console.log(twoSumOptimized([2,3,4], 6));
console.log(twoSumOptimized([-1,0], -1));
}
// File: javascript.optimized.js
// Problem: Two Sum II - Input array is sorted (LeetCode 167)
// Approach: Two-pointer (left/right) on sorted array — O(n) time, O(1) space
/**
* Optimized Two Sum II using two pointers.
* Since the input array is sorted in ascending order, we can use two pointers
* from both ends to find the pair that sums to the target.
* Returns 1-indexed positions [left+1, right+1] as per LeetCode 167.
*
* @param {number[]} numbers - sorted array of integers
* @param {number} target - target sum
* @returns {[number, number]} pair of 1-indexed positions
*/
function twoSumOptimized(numbers, target) {
let left = 0;
let right = numbers.length - 1;
while (left < right) {
const sum = numbers[left] + numbers[right];
if (sum === target) {
// Return 1-based indices
return [left + 1, right + 1];
}
if (sum < target) {
// Need a larger sum → move left pointer right
left++;
} else {
// sum > target → need a smaller sum → move right pointer left
right--;
}
}
return []; // LeetCode guarantees one solution in standard problem variants
}
// Runner & sample tests for local verification
if (typeof require !== 'undefined' && require.main === module) {
console.log('\nOptimized Two Sum II tests');
console.log(twoSumOptimized([2,7,11,15], 9)); // [1,2]
console.log(twoSumOptimized([2,3,4], 6)); // [1,3]
console.log(twoSumOptimized([-1,0], -1)); // [1,2]
}
/*
COMMENTS — Optimized (Two Sum II)
Why this solution:
- Uses the sorted property to find the pair in linear time.
- Two-pointer technique is canonical for sorted array pair-sum problems.
Interview talking points:
- Explain invariant: at each step, numbers[left] + numbers[right] is the current candidate sum.
If it's too small, increasing left increases sum; if too large, decreasing right decreases sum.
- Mention that positions are returned 1-indexed for LeetCode 167 and map back to original problem requirements.
Complexity:
- Time: O(n) since each pointer moves at most n steps in total.
- Space: O(1) auxiliary — only a few pointers/variables used.
*/
from typing import List, Tuple
def two_sum_brute(numbers: List[int], target: int) -> List[int]:
"""
Brute-force solution for Two Sum II (sorted array).
Tries every pair (i, j) with i < j and returns the first matching indices in 1-based format.
Args:
numbers: Sorted list of integers (ascending)
target: Target sum
Returns:
A list [i+1, j+1] with 1-based positions, or an empty list if no pair found.
Notes:
- This is primarily used as a correctness baseline. In interviews, present this first
then move to the optimized approach.
"""
n = len(numbers)
for i in range(n - 1):
for j in range(i + 1, n):
if numbers[i] + numbers[j] == target:
return [i + 1, j + 1]
return []
if __name__ == "__main__":
print('Brute-force Two Sum II tests')
print(two_sum_brute([2, 7, 11, 15], 9))
print(two_sum_brute([2, 3, 4], 6))
print(two_sum_brute([-1, 0], -1))
print(two_sum_brute([1, 2, 3], 7))
# File: python.brute.py
# Problem: Two Sum II - Input array is sorted (LeetCode 167)
# Approach: Brute-force nested loops (O(n^2))
# Returns 1-indexed positions as required by LeetCode 167
from typing import List, Tuple
def two_sum_brute(numbers: List[int], target: int) -> List[int]:
"""
Brute-force solution for Two Sum II (sorted array).
Tries every pair (i, j) with i < j and returns the first matching indices in 1-based format.
Args:
numbers: Sorted list of integers (ascending)
target: Target sum
Returns:
A list [i+1, j+1] with 1-based positions, or an empty list if no pair found.
Notes:
- This is primarily used as a correctness baseline. In interviews, present this first
then move to the optimized approach.
"""
n = len(numbers)
for i in range(n - 1):
# Optional micro-optimization: if numbers[i] > target and all numbers non-negative,
# you could break early. However, array may contain negatives, so we keep full checks.
for j in range(i + 1, n):
if numbers[i] + numbers[j] == target:
# Return 1-based indices
return [i + 1, j + 1]
return []
if __name__ == "__main__":
# Quick tests for local verification
print('Brute-force Two Sum II tests')
print(two_sum_brute([2, 7, 11, 15], 9)) # [1,2]
print(two_sum_brute([2, 3, 4], 6)) # [1,3]
print(two_sum_brute([-1, 0], -1)) # [1,2]
print(two_sum_brute([1, 2, 3], 7)) # []
# -----------------------
# COMMENTS — Brute (Two Sum II)
# -----------------------
# Why this solution:
# - Clear and easy to reason about: examines all pairs and proves correctness.
# - Useful to explain correctness on a whiteboard before optimising.
# Where to use:
# - As the baseline approach in interviews, or when n is guaranteed small.
# Complexity:
# - Time: O(n^2) because it checks all pairs (i < j).
# - Space: O(1) auxiliary.
# Interview notes:
# - Mention that since the array is sorted we can do better (two pointers).
# - If the problem doesn't require indices or the array isn't sorted, different optimizations apply (hash map etc.).
from typing import List
def two_sum_two_pointers(numbers: List[int], target: int) -> List[int]:
"""
Optimized Two Sum II using two pointers.
Since the input array is sorted in ascending order, two pointers from both ends
can find the pair that sums to the target in linear time.
Returns 1-indexed positions [left+1, right+1] as per LeetCode 167.
"""
left = 0
right = len(numbers) - 1
while left < right:
s = numbers[left] + numbers[right]
if s == target:
return [left + 1, right + 1]
if s < target:
left += 1
else:
right -= 1
return []
if __name__ == "__main__":
print('\nOptimized Two Sum II tests')
print(two_sum_two_pointers([2, 7, 11, 15], 9))
print(two_sum_two_pointers([2, 3, 4], 6))
print(two_sum_two_pointers([-1, 0], -1))
# File: python.optimized.py
# Problem: Two Sum II - Input array is sorted (LeetCode 167)
# Approach: Two-pointer (left/right) on sorted array — O(n) time, O(1) space
from typing import List
def two_sum_two_pointers(numbers: List[int], target: int) -> List[int]:
"""
Optimized Two Sum II using two pointers.
Since the input array is sorted in ascending order, two pointers from both ends
can find the pair that sums to the target in linear time.
Returns 1-indexed positions [left+1, right+1] as per LeetCode 167.
"""
left = 0
right = len(numbers) - 1
while left < right:
s = numbers[left] + numbers[right]
if s == target:
return [left + 1, right + 1]
if s < target:
# Need a larger sum → move left pointer right
left += 1
else:
# s > target → need a smaller sum → move right pointer left
right -= 1
return [] # LeetCode typically guarantees a solution
if __name__ == "__main__":
# Quick tests for local verification
print('\nOptimized Two Sum II tests')
print(two_sum_two_pointers([2, 7, 11, 15], 9)) # [1,2]
print(two_sum_two_pointers([2, 3, 4], 6)) # [1,3]
print(two_sum_two_pointers([-1, 0], -1)) # [1,2]
# -----------------------
# COMMENTS — Optimized (Two Sum II)
# -----------------------
# Why this solution:
# - Leverages sorted property to achieve linear time.
# - Two-pointer technique is canonical for sorted array pair-sum problems.
# Complexity:
# - Time: O(n) because each pointer moves at most n times total.
# - Space: O(1) auxiliary.
# Interview talking points:
# - Explain invariant: current sum = numbers[left] + numbers[right].
# If sum is smaller than target, increasing left increases sum; if larger, decreasing right decreases sum.
# - Mention that indices for this problem are 1-based; be careful to map back when returning results.
# - If the variant requires original indices with unsorted input, sorting loses original positions; use hash map instead.
class SolutionBrute {
public int[] twoSum(int[] numbers, int target) {
int n = numbers.length;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (numbers[i] + numbers[j] == target) {
return new int[]{i + 1, j + 1};
}
}
}
return new int[]{-1, -1};
}
public static void main(String[] args) {
SolutionBrute sol = new SolutionBrute();
int[] res1 = sol.twoSum(new int[]{2, 7, 11, 15}, 9);
System.out.println("Brute test1: " + res1[0] + "," + res1[1]);
int[] res2 = sol.twoSum(new int[]{2, 3, 4}, 6);
System.out.println("Brute test2: " + res2[0] + "," + res2[1]);
}
}
// File: java.brute.java
// Brute-force solution for Two Sum II (LeetCode 167)
// Time: O(n^2) — try all pairs (i, j)
// Space: O(1) extra space
/**
* Brute-force implementation for Two Sum II.
* Loops over all pairs i < j, checks if numbers[i] + numbers[j] == target.
*
* NOTE:
* - Input array is sorted, but brute force ignores that fact.
* - Useful as a baseline to demonstrate correctness in interviews.
*/
class SolutionBrute {
public int[] twoSum(int[] numbers, int target) {
int n = numbers.length;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (numbers[i] + numbers[j] == target) {
// Return 1-based indices as required by problem
return new int[]{i + 1, j + 1};
}
}
}
// Problem guarantees a solution exists, so this return is just safety
return new int[]{-1, -1};
}
// Quick test runner
public static void main(String[] args) {
SolutionBrute sol = new SolutionBrute();
int[] res1 = sol.twoSum(new int[]{2, 7, 11, 15}, 9); // [1,2]
System.out.println("Brute test1: " + res1[0] + "," + res1[1]);
int[] res2 = sol.twoSum(new int[]{2, 3, 4}, 6); // [1,3]
System.out.println("Brute test2: " + res2[0] + "," + res2[1]);
}
}
/*
COMMENTS — Brute Force
----------------------
Why: Simple to implement, demonstrates correctness without leveraging "sorted" property.
Where to use:
- First baseline approach in interviews.
- When n is very small.
Complexity:
- Time: O(n^2) due to checking all pairs.
- Space: O(1) extra.
*/
class SolutionOptimized {
public int[] twoSum(int[] numbers, int target) {
int left = 0;
int right = numbers.length - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
return new int[]{left + 1, right + 1};
} else if (sum < target) {
left++;
} else {
right--;
}
}
return new int[]{-1, -1};
}
public static void main(String[] args) {
SolutionOptimized sol = new SolutionOptimized();
int[] res1 = sol.twoSum(new int[]{2, 7, 11, 15}, 9);
System.out.println("Optimized test1: " + res1[0] + "," + res1[1]);
int[] res2 = sol.twoSum(new int[]{2, 3, 4}, 6);
System.out.println("Optimized test2: " + res2[0] + "," + res2[1]);
}
}
// File: java.optimized.java
// Optimized Two-pointer solution for Two Sum II (LeetCode 167)
// Time: O(n) — single pass with two pointers
// Space: O(1) — constant extra space
/**
* Optimized solution leveraging the sorted array property.
* Uses two pointers:
* - left starts at beginning, right starts at end.
* - Move left/right depending on whether sum < or > target.
*
* Invariant: At each step, [left, right] is the current candidate pair.
*/
class SolutionOptimized {
public int[] twoSum(int[] numbers, int target) {
int left = 0;
int right = numbers.length - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
return new int[]{left + 1, right + 1}; // 1-based indexing
} else if (sum < target) {
left++; // Need bigger sum → move left forward
} else {
right--; // Need smaller sum → move right backward
}
}
return new int[]{-1, -1}; // safety
}
// Quick test runner
public static void main(String[] args) {
SolutionOptimized sol = new SolutionOptimized();
int[] res1 = sol.twoSum(new int[]{2, 7, 11, 15}, 9); // [1,2]
System.out.println("Optimized test1: " + res1[0] + "," + res1[1]);
int[] res2 = sol.twoSum(new int[]{2, 3, 4}, 6); // [1,3]
System.out.println("Optimized test2: " + res2[0] + "," + res2[1]);
}
}
/*
COMMENTS — Optimized
--------------------
Why: Exploits sorted property, achieves O(n).
Where to use:
- Default interview solution for Two Sum II.
- Best tradeoff: linear time, constant space.
Complexity:
- Time: O(n). Each pointer moves at most n steps.
- Space: O(1). No auxiliary data structures.
*/
#include <iostream>
#include <vector>
using namespace std;
class SolutionBrute {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int n = numbers.size();
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (numbers[i] + numbers[j] == target) {
return {i + 1, j + 1};
}
}
}
return {-1, -1};
}
};
int main() {
SolutionBrute sol;
vector<int> nums1 = {2,7,11,15};
auto res1 = sol.twoSum(nums1, 9);
cout << "Brute test1: " << res1[0] << "," << res1[1] << endl;
vector<int> nums2 = {2,3,4};
auto res2 = sol.twoSum(nums2, 6);
cout << "Brute test2: " << res2[0] << "," << res2[1] << endl;
return 0;
}
// File: cpp.brute.cpp
// Brute-force solution for Two Sum II (LeetCode 167)
// Time: O(n^2), Space: O(1)
#include <iostream>
#include <vector>
using namespace std;
/**
* Brute force: try all pairs i < j.
* Return 1-based indices when a match is found.
*/
class SolutionBrute {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int n = numbers.size();
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (numbers[i] + numbers[j] == target) {
return {i + 1, j + 1};
}
}
}
return {-1, -1};
}
};
// Simple test runner
int main() {
SolutionBrute sol;
vector<int> nums1 = {2,7,11,15};
auto res1 = sol.twoSum(nums1, 9);
cout << "Brute test1: " << res1[0] << "," << res1[1] << endl;
vector<int> nums2 = {2,3,4};
auto res2 = sol.twoSum(nums2, 6);
cout << "Brute test2: " << res2[0] << "," << res2[1] << endl;
return 0;
}
/*
COMMENTS — Brute
----------------
- Simple, checks all pairs.
- Demonstrates correctness.
- O(n^2) time, O(1) space.
*/
#include <iostream>
#include <vector>
using namespace std;
class SolutionOptimized {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int left = 0;
int right = numbers.size() - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
return {left + 1, right + 1};
} else if (sum < target) {
left++;
} else {
right--;
}
}
return {-1, -1};
}
};
int main() {
SolutionOptimized sol;
vector<int> nums1 = {2,7,11,15};
auto res1 = sol.twoSum(nums1, 9);
cout << "Optimized test1: " << res1[0] << "," << res1[1] << endl;
vector<int> nums2 = {2,3,4};
auto res2 = sol.twoSum(nums2, 6);
cout << "Optimized test2: " << res2[0] << "," << res2[1] << endl;
return 0;
}
// File: cpp.optimized.cpp
// Optimized Two-pointer solution for Two Sum II (LeetCode 167)
// Time: O(n), Space: O(1)
#include <iostream>
#include <vector>
using namespace std;
/**
* Optimized approach:
* - Left pointer at start, right pointer at end.
* - Shrink/move pointers based on current sum vs target.
*/
class SolutionOptimized {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int left = 0;
int right = numbers.size() - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
return {left + 1, right + 1};
} else if (sum < target) {
left++;
} else {
right--;
}
}
return {-1, -1};
}
};
// Simple test runner
int main() {
SolutionOptimized sol;
vector<int> nums1 = {2,7,11,15};
auto res1 = sol.twoSum(nums1, 9);
cout << "Optimized test1: " << res1[0] << "," << res1[1] << endl;
vector<int> nums2 = {2,3,4};
auto res2 = sol.twoSum(nums2, 6);
cout << "Optimized test2: " << res2[0] << "," << res2[1] << endl;
return 0;
}
/*
COMMENTS — Optimized
--------------------
- Exploits sorted property.
- Linear scan with two pointers.
- O(n) time, O(1) space.
- Best practical solution for interviews.
*/
using System;
namespace TwoSumII_Brute {
public class SolutionBrute {
public int[] TwoSum(int[] numbers, int target) {
int n = numbers.Length;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (numbers[i] + numbers[j] == target) {
return new int[] { i + 1, j + 1 };
}
}
}
return new int[] { -1, -1 };
}
public static void Main(string[] args) {
var sol = new SolutionBrute();
var res1 = sol.TwoSum(new int[] { 2, 7, 11, 15 }, 9);
Console.WriteLine($"Brute test1: {res1[0]},{res1[1]}");
var res2 = sol.TwoSum(new int[] { 2, 3, 4 }, 6);
Console.WriteLine($"Brute test2: {res2[0]},{res2[1]}");
}
}
}
// File: csharp.brute.cs
// Problem: Two Sum II - Input array is sorted (LeetCode 167)
// Approach: Brute-force nested loops (O(n^2))
// Returns 1-indexed positions as required by LeetCode 167
using System;
namespace TwoSumII_Brute {
public class SolutionBrute {
/// <summary>
/// Brute-force solution for Two Sum II (sorted array).
/// Tries every pair (i, j) with i < j and returns first matching indices in 1-based format.
/// Useful for correctness baseline in interviews.
/// </summary>
/// <param name="numbers">Sorted array of integers (ascending)</param>
/// <param name="target">Target sum</param>
/// <returns>int[] of size 2 with 1-based positions or empty array</returns>
public int[] TwoSum(int[] numbers, int target) {
int n = numbers.Length;
for (int i = 0; i < n - 1; i++) {
// Micro-note: if numbers are all positive and numbers[i] > target, you might early-break.
for (int j = i + 1; j < n; j++) {
if (numbers[i] + numbers[j] == target) {
// Return 1-based indices per LeetCode 167
return new int[] { i + 1, j + 1 };
}
}
}
// Problem usually guarantees a solution; return sentinel for safety
return new int[] { -1, -1 };
}
// Quick runner to test locally
public static void Main(string[] args) {
var sol = new SolutionBrute();
var res1 = sol.TwoSum(new int[] { 2, 7, 11, 15 }, 9); // [1,2]
Console.WriteLine($"Brute test1: {res1[0]},{res1[1]}");
var res2 = sol.TwoSum(new int[] { 2, 3, 4 }, 6); // [1,3]
Console.WriteLine($"Brute test2: {res2[0]},{res2[1]}");
}
}
}
/*
COMMENTS — Brute (C#)
Why this solution:
- Straightforward and demonstrates correctness by exhaustively checking pairs.
When to present in interview:
- Show as a baseline, then explain why we need optimization (use sorted property).
Complexity:
- Time: O(n^2) — checks O(n^2) pairs.
- Space: O(1) auxiliary.
Interview tips:
- Mention possible micro-optimizations (early breaks when applicable) but clarify why they may not be safe if negatives exist.
- Always clarify that the problem requires 1-based indices for Two Sum II on LeetCode.
*/
using System;
namespace TwoSumII_Optimized {
public class SolutionOptimized {
public int[] TwoSum(int[] numbers, int target) {
int left = 0;
int right = numbers.Length - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
return new int[] { left + 1, right + 1 };
}
if (sum < target) {
left++;
} else {
right--;
}
}
return new int[] { -1, -1 };
}
public static void Main(string[] args) {
var sol = new SolutionOptimized();
var r1 = sol.TwoSum(new int[] { 2, 7, 11, 15 }, 9);
Console.WriteLine($"Optimized test1: {r1[0]},{r1[1]}");
var r2 = sol.TwoSum(new int[] { 2, 3, 4 }, 6);
Console.WriteLine($"Optimized test2: {r2[0]},{r2[1]}");
}
}
}
// File: csharp.optimized.cs
// Problem: Two Sum II - Input array is sorted (LeetCode 167)
// Approach: Two-pointer (left/right) — O(n) time, O(1) auxiliary space
using System;
namespace TwoSumII_Optimized {
public class SolutionOptimized {
/// <summary>
/// Two-pointer approach leveraging the sorted property of the array.
/// Returns 1-based indices as required by LeetCode 167.
/// </summary>
public int[] TwoSum(int[] numbers, int target) {
int left = 0;
int right = numbers.Length - 1;
// Invariant: at each step, we consider pair (left, right)
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
// Found exact pair
return new int[] { left + 1, right + 1 };
}
if (sum < target) {
// Need larger sum -> move left forward
left++;
} else {
// sum > target -> need smaller sum -> move right backward
right--;
}
}
// LeetCode variant guarantees one solution usually; return sentinel if not found
return new int[] { -1, -1 };
}
// Runner for local testing
public static void Main(string[] args) {
var sol = new SolutionOptimized();
var r1 = sol.TwoSum(new int[] { 2, 7, 11, 15 }, 9);
Console.WriteLine($"Optimized test1: {r1[0]},{r1[1]}");
var r2 = sol.TwoSum(new int[] { 2, 3, 4 }, 6);
Console.WriteLine($"Optimized test2: {r2[0]},{r2[1]}");
}
}
}
/*
COMMENTS — Optimized (C#)
Why this solution:
- Efficient O(n) solution using two-pointer pattern for sorted arrays.
Interview notes:
- Explain the pointer invariant: if sum < target, moving left increases sum; if sum > target, moving right decreases sum.
- If indices were 0-based in a variant, adjust accordingly. Be explicit about 1-based requirement in LC167.
Complexity:
- Time: O(n) — each pointer moves at most n steps together.
- Space: O(1) auxiliary.
*/
package main
import "fmt"
func twoSumBrute(numbers []int, target int) []int {
n := len(numbers)
for i := 0; i < n-1; i++ {
for j := i + 1; j < n; j++ {
if numbers[i]+numbers[j] == target {
return []int{i + 1, j + 1}
}
}
}
return []int{}
}
func main() {
fmt.Println("Brute-force Two Sum II tests")
fmt.Println(twoSumBrute([]int{2, 7, 11, 15}, 9))
fmt.Println(twoSumBrute([]int{2, 3, 4}, 6))
fmt.Println(twoSumBrute([]int{-1, 0}, -1))
}
// File: go.brute.go
// Problem: Two Sum II - Input array is sorted (LeetCode 167)
// Approach: Brute-force nested loops (O(n^2))
// Returns 1-indexed positions per LeetCode requirement
package main
import "fmt"
// twoSumBrute tries all pairs (i, j) where i < j and returns 1-based indices
func twoSumBrute(numbers []int, target int) []int {
n := len(numbers)
for i := 0; i < n-1; i++ {
for j := i + 1; j < n; j++ {
if numbers[i]+numbers[j] == target {
return []int{i + 1, j + 1}
}
}
}
return []int{}
}
func main() {
fmt.Println("Brute-force Two Sum II tests")
fmt.Println(twoSumBrute([]int{2, 7, 11, 15}, 9)) // [1,2]
fmt.Println(twoSumBrute([]int{2, 3, 4}, 6)) // [1,3]
fmt.Println(twoSumBrute([]int{-1, 0}, -1)) // [1,2]
}
/*
COMMENTS — Brute (Go)
Why this solution:
- Straightforward baseline to show correctness.
When to use in interview:
- Present as initial correct approach, then optimize using sorted property.
Complexity:
- Time: O(n^2)
- Space: O(1) auxiliary
*/
package main
import "fmt"
func twoSumTwoPointers(numbers []int, target int) []int {
left := 0
right := len(numbers) - 1
for left < right {
sum := numbers[left] + numbers[right]
if sum == target {
return []int{left + 1, right + 1}
}
if sum < target {
left++
} else {
right--
}
}
return []int{}
}
func main() {
fmt.Println("Optimized Two Sum II tests")
fmt.Println(twoSumTwoPointers([]int{2, 7, 11, 15}, 9))
fmt.Println(twoSumTwoPointers([]int{2, 3, 4}, 6))
fmt.Println(twoSumTwoPointers([]int{-1, 0}, -1))
}
// File: go.optimized.go
// Problem: Two Sum II - Input array is sorted (LeetCode 167)
// Approach: Two-pointer (left/right) — O(n) time, O(1) space
package main
import "fmt"
// twoSumTwoPointers returns 1-based indices of pair summing to target
func twoSumTwoPointers(numbers []int, target int) []int {
left := 0
right := len(numbers) - 1
for left < right {
sum := numbers[left] + numbers[right]
if sum == target {
return []int{left + 1, right + 1}
}
if sum < target {
left++
} else {
right--
}
}
return []int{}
}
func main() {
fmt.Println("Optimized Two Sum II tests")
fmt.Println(twoSumTwoPointers([]int{2, 7, 11, 15}, 9)) // [1,2]
fmt.Println(twoSumTwoPointers([]int{2, 3, 4}, 6)) // [1,3]
fmt.Println(twoSumTwoPointers([]int{-1, 0}, -1)) // [1,2]
}
/*
COMMENTS — Optimized (Go)
Why this solution:
- Leverages sorted input to run in linear time using two pointers.
Complexity:
- Time: O(n), Space: O(1)
Interview notes:
- Explain pointer movement invariants: moving left increases sum; moving right decreases sum.
- Clarify 1-based indexing for Two Sum II when returning results.
*/
export function twoSumBrute(numbers: number[], target: number): number[] {
const n = numbers.length;
for (let i = 0; i < n - 1; i++) {
for (let j = i + 1; j < n; j++) {
if (numbers[i] + numbers[j] === target) {
return [i + 1, j + 1];
}
}
}
return [];
}
if (require && require.main === module) {
console.log('Brute-force Two Sum II tests');
console.log(twoSumBrute([2,7,11,15], 9));
console.log(twoSumBrute([2,3,4], 6));
}
// File: typescript.brute.ts
// Problem: Two Sum II - Input array is sorted (LeetCode 167)
// Approach: Brute-force nested loops (O(n^2))
// Returns 1-based indices as required by LeetCode 167
export function twoSumBrute(numbers: number[], target: number): number[] {
const n = numbers.length;
for (let i = 0; i < n - 1; i++) {
for (let j = i + 1; j < n; j++) {
if (numbers[i] + numbers[j] === target) {
return [i + 1, j + 1];
}
}
}
return [];
}
if (require && require.main === module) {
console.log('Brute-force Two Sum II tests');
console.log(twoSumBrute([2,7,11,15], 9)); // [1,2]
console.log(twoSumBrute([2,3,4], 6)); // [1,3]
}
/*
COMMENTS — Brute (TypeScript)
- Baseline approach; explain correctness before optimizing.
- Time: O(n^2), Space: O(1).
*/
export function twoSumTwoPointers(numbers: number[], target: number): number[] {
let left = 0;
let right = numbers.length - 1;
while (left < right) {
const sum = numbers[left] + numbers[right];
if (sum === target) return [left + 1, right + 1];
if (sum < target) left++; else right--;
}
return [];
}
if (require && require.main === module) {
console.log('\nOptimized Two Sum II tests');
console.log(twoSumTwoPointers([2,7,11,15], 9));
console.log(twoSumTwoPointers([2,3,4], 6));
}
// File: typescript.optimized.ts
// Problem: Two Sum II - Input array is sorted (LeetCode 167)
// Approach: Two-pointer (left/right) — O(n) time, O(1) space
export function twoSumTwoPointers(numbers: number[], target: number): number[] {
let left = 0;
let right = numbers.length - 1;
while (left < right) {
const sum = numbers[left] + numbers[right];
if (sum === target) return [left + 1, right + 1];
if (sum < target) left++; else right--;
}
return [];
}
if (require && require.main === module) {
console.log('\nOptimized Two Sum II tests');
console.log(twoSumTwoPointers([2,7,11,15], 9)); // [1,2]
console.log(twoSumTwoPointers([2,3,4], 6)); // [1,3]
}
/*
COMMENTS — Optimized (TypeScript)
- Preferred solution for sorted input: O(n) time, O(1) space.
- Interview tip: clarify 1-based return indices for LC167.
*/
def two_sum_brute(numbers, target)
n = numbers.length
(0...(n - 1)).each do |i|
((i + 1)...n).each do |j|
if numbers[i] + numbers[j] == target
return [i + 1, j + 1]
end
end
end
[]
end
if __FILE__ == $0
puts 'Brute-force Two Sum II tests'
p two_sum_brute([2,7,11,15], 9)
p two_sum_brute([2,3,4], 6)
p two_sum_brute([-1,0], -1)
end
# File: ruby.brute.rb
# Problem: Two Sum II - Input array is sorted (LeetCode 167)
# Approach: Brute-force nested loops (O(n^2))
# Returns 1-based positions as required by LeetCode 167
def two_sum_brute(numbers, target)
n = numbers.length
(0...(n - 1)).each do |i|
((i + 1)...n).each do |j|
if numbers[i] + numbers[j] == target
return [i + 1, j + 1] # 1-based indices
end
end
end
[]
end
if __FILE__ == $0
puts 'Brute-force Two Sum II tests'
p two_sum_brute([2,7,11,15], 9) # [1,2]
p two_sum_brute([2,3,4], 6) # [1,3]
p two_sum_brute([-1,0], -1) # [1,2]
end
=begin
COMMENTS — Brute (Ruby)
Why this solution:
- Simple and clear. Good baseline to explain correctness on whiteboard.
Interview tips:
- Show brute-force first then explain optimization leveraging sorted input.
Complexity:
- Time: O(n^2)
- Space: O(1) auxiliary
=end
def two_sum_two_pointers(numbers, target)
left = 0
right = numbers.length - 1
while left < right
sum = numbers[left] + numbers[right]
if sum == target
return [left + 1, right + 1]
elsif sum < target
left += 1
else
right -= 1
end
end
[]
end
if __FILE__ == $0
puts 'Optimized Two Sum II tests'
p two_sum_two_pointers([2,7,11,15], 9)
p two_sum_two_pointers([2,3,4], 6)
p two_sum_two_pointers([-1,0], -1)
end
# File: ruby.optimized.rb
# Problem: Two Sum II - Input array is sorted (LeetCode 167)
# Approach: Two-pointer (left/right) — O(n) time, O(1) space
def two_sum_two_pointers(numbers, target)
left = 0
right = numbers.length - 1
while left < right
sum = numbers[left] + numbers[right]
if sum == target
return [left + 1, right + 1] # 1-based
elsif sum < target
left += 1
else
right -= 1
end
end
[]
end
if __FILE__ == $0
puts 'Optimized Two Sum II tests'
p two_sum_two_pointers([2,7,11,15], 9) # [1,2]
p two_sum_two_pointers([2,3,4], 6) # [1,3]
p two_sum_two_pointers([-1,0], -1) # [1,2]
end
=begin
COMMENTS — Optimized (Ruby)
Why this solution:
- Efficient: uses sorted property and two-pointer technique for linear time.
Complexity:
- Time: O(n), Space: O(1)
Interview notes:
- Explain pointer movement: left++ increases sum, right-- decreases sum.
- Remember to return 1-based indices for LC167.
=end
import Foundation
func twoSumBrute(_ numbers: [Int], _ target: Int) -> [Int] {
let n = numbers.count
for i in 0..<(n - 1) {
for j in (i + 1)..<n {
if numbers[i] + numbers[j] == target {
return [i + 1, j + 1]
}
}
}
return []
}
if CommandLine.arguments.count == 1 {
print("Brute-force Two Sum II tests")
print(twoSumBrute([2, 7, 11, 15], 9))
print(twoSumBrute([2, 3, 4], 6))
print(twoSumBrute([-1, 0], -1))
}
// File: swift.brute.swift
// Problem: Two Sum II - Input array is sorted (LeetCode 167)
// Approach: Brute-force nested loops (O(n^2))
// Returns 1-based indices as required by LeetCode 167
import Foundation
func twoSumBrute(_ numbers: [Int], _ target: Int) -> [Int] {
let n = numbers.count
for i in 0..<(n - 1) {
for j in (i + 1)..<n {
if numbers[i] + numbers[j] == target {
// Return 1-based positions
return [i + 1, j + 1]
}
}
}
return [] // Safety fallback; problem usually guarantees a solution
}
// Quick tests for local execution
if CommandLine.arguments.count == 1 {
print("Brute-force Two Sum II tests")
print(twoSumBrute([2, 7, 11, 15], 9)) // [1,2]
print(twoSumBrute([2, 3, 4], 6)) // [1,3]
print(twoSumBrute([-1, 0], -1)) // [1,2]
}
/*
COMMENTS — Brute (Swift)
Why this solution:
- Explicitly checks all pairs and is easy to explain on a whiteboard.
When to use:
- Demonstrate baseline correctness in interviews before optimizing.
Complexity:
- Time: O(n^2) since it evaluates roughly n*(n-1)/2 pairs.
- Space: O(1) auxiliary.
Interview notes:
- Mention that although input is sorted, this brute solution doesn't exploit that; next step is two-pointer.
- If numbers can be large, show how early-break heuristics might work for non-negative arrays.
*/
import Foundation
func twoSumTwoPointers(_ numbers: [Int], _ target: Int) -> [Int] {
var left = 0
var right = numbers.count - 1
while left < right {
let sum = numbers[left] + numbers[right]
if sum == target {
return [left + 1, right + 1]
} else if sum < target {
left += 1
} else {
right -= 1
}
}
return []
}
if CommandLine.arguments.count == 1 {
print("Optimized Two Sum II tests")
print(twoSumTwoPointers([2, 7, 11, 15], 9))
print(twoSumTwoPointers([2, 3, 4], 6))
print(twoSumTwoPointers([-1, 0], -1))
}
// File: swift.optimized.swift
// Problem: Two Sum II - Input array is sorted (LeetCode 167)
// Approach: Two-pointer technique — O(n) time, O(1) space
import Foundation
func twoSumTwoPointers(_ numbers: [Int], _ target: Int) -> [Int] {
var left = 0
var right = numbers.count - 1
while left < right {
let sum = numbers[left] + numbers[right]
if sum == target {
return [left + 1, right + 1] // 1-based indexing per problem
} else if sum < target {
left += 1 // increase sum by moving left right
} else {
right -= 1 // decrease sum by moving right left
}
}
return []
}
// Quick tests
if CommandLine.arguments.count == 1 {
print("Optimized Two Sum II tests")
print(twoSumTwoPointers([2, 7, 11, 15], 9)) // [1,2]
print(twoSumTwoPointers([2, 3, 4], 6)) // [1,3]
print(twoSumTwoPointers([-1, 0], -1)) // [1,2]
}
/*
COMMENTS — Optimized (Swift)
Why this solution:
- Utilizes sorted property for linear time solution.
- Two-pointer approach is idiomatic and efficient.
Complexity:
- Time: O(n) — each pointer moves at most n steps.
- Space: O(1) auxiliary.
Interview talking points:
- Explain pointer invariant: if sum < target, moving left increases sum; if sum > target, moving right decreases sum.
- Confirm 1-based indexing requirement on return values for LC167. If variant asks 0-based indices, adjust accordingly.
*/
fun twoSumBrute(numbers: IntArray, target: Int): IntArray {
val n = numbers.size
for (i in 0 until n - 1) {
for (j in i + 1 until n) {
if (numbers[i] + numbers[j] == target) {
return intArrayOf(i + 1, j + 1)
}
}
}
return intArrayOf(-1, -1)
}
fun main() {
println("Brute-force Two Sum II tests")
println(twoSumBrute(intArrayOf(2, 7, 11, 15), 9).joinToString(","))
println(twoSumBrute(intArrayOf(2, 3, 4), 6).joinToString(","))
println(twoSumBrute(intArrayOf(-1, 0), -1).joinToString(","))
}
// File: kotlin.brute.kt
// Problem: Two Sum II - Input array is sorted (LeetCode 167)
// Approach: Brute-force nested loops (O(n^2))
// Returns 1-based indices as required by LeetCode 167
fun twoSumBrute(numbers: IntArray, target: Int): IntArray {
val n = numbers.size
for (i in 0 until n - 1) {
for (j in i + 1 until n) {
if (numbers[i] + numbers[j] == target) {
// Return 1-based indices
return intArrayOf(i + 1, j + 1)
}
}
}
return intArrayOf(-1, -1) // safety fallback
}
fun main() {
println("Brute-force Two Sum II tests")
println(twoSumBrute(intArrayOf(2, 7, 11, 15), 9).joinToString(",")) // [1,2]
println(twoSumBrute(intArrayOf(2, 3, 4), 6).joinToString(",")) // [1,3]
println(twoSumBrute(intArrayOf(-1, 0), -1).joinToString(",")) // [1,2]
}
/*
COMMENTS — Brute (Kotlin)
Why this solution:
- Explicit and easy to reason about; shows correctness by checking all pairs.
Interview guidance:
- Present brute-force first on whiteboard to show correctness, then optimize using sorted property.
Complexity:
- Time: O(n^2)
- Space: O(1) auxiliary
*/
fun twoSumTwoPointers(numbers: IntArray, target: Int): IntArray {
var left = 0
var right = numbers.size - 1
while (left < right) {
val sum = numbers[left] + numbers[right]
if (sum == target) {
return intArrayOf(left + 1, right + 1)
}
if (sum < target) left++ else right--
}
return intArrayOf(-1, -1)
}
fun main() {
println("Optimized Two Sum II tests")
println(twoSumTwoPointers(intArrayOf(2, 7, 11, 15), 9).joinToString(","))
println(twoSumTwoPointers(intArrayOf(2, 3, 4), 6).joinToString(","))
println(twoSumTwoPointers(intArrayOf(-1, 0), -1).joinToString(","))
}
// File: kotlin.optimized.kt
// Problem: Two Sum II - Input array is sorted (LeetCode 167)
// Approach: Two-pointer (left/right) — O(n) time, O(1) space
fun twoSumTwoPointers(numbers: IntArray, target: Int): IntArray {
var left = 0
var right = numbers.size - 1
while (left < right) {
val sum = numbers[left] + numbers[right]
if (sum == target) {
return intArrayOf(left + 1, right + 1) // 1-based
}
if (sum < target) left++ else right--
}
return intArrayOf(-1, -1)
}
fun main() {
println("Optimized Two Sum II tests")
println(twoSumTwoPointers(intArrayOf(2, 7, 11, 15), 9).joinToString(",")) // [1,2]
println(twoSumTwoPointers(intArrayOf(2, 3, 4), 6).joinToString(",")) // [1,3]
println(twoSumTwoPointers(intArrayOf(-1, 0), -1).joinToString(",")) // [1,2]
}
/*
COMMENTS — Optimized (Kotlin)
Why this solution:
- Uses sorted property to find pair in linear time via two pointers.
Interview notes:
- Explain pointer invariant: moving left increases sum, moving right decreases sum.
- Mention 1-based index requirement for LeetCode 167.
Complexity:
- Time: O(n)
- Space: O(1)
*/
object ScalaBrute {
def twoSum(numbers: Array[Int], target: Int): Array[Int] = {
val n = numbers.length
for (i <- 0 until n - 1) {
for (j <- i + 1 until n) {
if (numbers(i) + numbers(j) == target) {
return Array(i + 1, j + 1)
}
}
}
Array(-1, -1)
}
def main(args: Array[String]): Unit = {
println("Brute-force Two Sum II tests")
println(twoSum(Array(2,7,11,15), 9).mkString(","))
println(twoSum(Array(2,3,4), 6).mkString(","))
}
}
// File: scala.brute.scala
// Problem: Two Sum II - Input array is sorted (LeetCode 167)
// Approach: Brute-force nested loops (O(n^2))
// Returns 1-based indices as required by LeetCode 167
object ScalaBrute {
def twoSum(numbers: Array[Int], target: Int): Array[Int] = {
val n = numbers.length
for (i <- 0 until n - 1) {
for (j <- i + 1 until n) {
if (numbers(i) + numbers(j) == target) {
// Return 1-based indices
return Array(i + 1, j + 1)
}
}
}
Array(-1, -1)
}
def main(args: Array[String]): Unit = {
println("Brute-force Two Sum II tests")
println(twoSum(Array(2,7,11,15), 9).mkString(",")) // [1,2]
println(twoSum(Array(2,3,4), 6).mkString(",")) // [1,3]
}
}
/*
COMMENTS — Brute (Scala)
- Straightforward baseline to demonstrate correctness.
- Time: O(n^2), Space: O(1).
- Interview tip: explain brute then optimize using two-pointer.
*/
object ScalaOptimized {
def twoSum(numbers: Array[Int], target: Int): Array[Int] = {
var left = 0
var right = numbers.length - 1
while (left < right) {
val sum = numbers(left) + numbers(right)
if (sum == target) return Array(left + 1, right + 1)
else if (sum < target) left += 1
else right -= 1
}
Array(-1, -1)
}
def main(args: Array[String]): Unit = {
println("Optimized Two Sum II tests")
println(twoSum(Array(2,7,11,15), 9).mkString(","))
println(twoSum(Array(2,3,4), 6).mkString(","))
}
}
// File: scala.optimized.scala
// Problem: Two Sum II - Input array is sorted (LeetCode 167)
// Approach: Two-pointer (left/right) — O(n) time, O(1) space
object ScalaOptimized {
def twoSum(numbers: Array[Int], target: Int): Array[Int] = {
var left = 0
var right = numbers.length - 1
while (left < right) {
val sum = numbers(left) + numbers(right)
if (sum == target) return Array(left + 1, right + 1)
else if (sum < target) left += 1
else right -= 1
}
Array(-1, -1)
}
def main(args: Array[String]): Unit = {
println("Optimized Two Sum II tests")
println(twoSum(Array(2,7,11,15), 9).mkString(",")) // [1,2]
println(twoSum(Array(2,3,4), 6).mkString(",")) // [1,3]
}
}
/*
COMMENTS — Optimized (Scala)
- Uses sorted property for linear-time solution.
- Time: O(n), Space: O(1).
- Interview tip: discuss pointer invariant and 1-based indexing.
*/
fn two_sum_brute(numbers: &[i32], target: i32) -> Option<(usize, usize)> {
let n = numbers.len();
for i in 0..n.saturating_sub(1) {
for j in (i + 1)..n {
if numbers[i] + numbers[j] == target {
return Some((i + 1, j + 1));
}
}
}
None
}
fn main() {
println!("Brute-force Two Sum II tests");
println!("{:?}", two_sum_brute(&[2, 7, 11, 15], 9));
println!("{:?}", two_sum_brute(&[2, 3, 4], 6));
println!("{:?}", two_sum_brute(&[-1, 0], -1));
}
// File: rust.brute.rs
// Problem: Two Sum II - Input array is sorted (LeetCode 167)
// Approach: Brute-force nested loops (O(n^2))
// Returns 1-based indices per LeetCode requirement
fn two_sum_brute(numbers: &[i32], target: i32) -> Option<(usize, usize)> {
let n = numbers.len();
for i in 0..n.saturating_sub(1) {
for j in (i + 1)..n {
if numbers[i] + numbers[j] == target {
// Return 1-based positions wrapped in Option
return Some((i + 1, j + 1));
}
}
}
None
}
fn main() {
println!("Brute-force Two Sum II tests");
println!("{:?}", two_sum_brute(&[2, 7, 11, 15], 9)); // Some((1,2))
println!("{:?}", two_sum_brute(&[2, 3, 4], 6)); // Some((1,3))
println!("{:?}", two_sum_brute(&[-1, 0], -1)); // Some((1,2))
}
/*
COMMENTS — Brute (Rust)
Why this solution:
- Simple baseline to demonstrate correctness.
Complexity:
- Time: O(n^2)
- Space: O(1) auxiliary
Interview notes:
- Mention safety and bounds checks; using slices avoids ownership complexities in examples.
*/
fn two_sum_two_pointers(numbers: &[i32], target: i32) -> Option<(usize, usize)> {
let mut left: isize = 0;
let mut right: isize = (numbers.len() as isize) - 1;
while left < right {
let sum = numbers[left as usize] + numbers[right as usize];
if sum == target {
return Some(((left as usize) + 1, (right as usize) + 1));
} else if sum < target {
left += 1;
} else {
right -= 1;
}
}
None
}
fn main() {
println!("Optimized Two Sum II tests");
println!("{:?}", two_sum_two_pointers(&[2, 7, 11, 15], 9));
println!("{:?}", two_sum_two_pointers(&[2, 3, 4], 6));
println!("{:?}", two_sum_two_pointers(&[-1, 0], -1));
}
// File: rust.optimized.rs
// Problem: Two Sum II - Input array is sorted (LeetCode 167)
// Approach: Two-pointer (left/right) — O(n) time, O(1) space
fn two_sum_two_pointers(numbers: &[i32], target: i32) -> Option<(usize, usize)> {
let mut left: isize = 0;
let mut right: isize = (numbers.len() as isize) - 1;
while left < right {
let sum = numbers[left as usize] + numbers[right as usize];
if sum == target {
return Some(((left as usize) + 1, (right as usize) + 1)); // 1-based
} else if sum < target {
left += 1;
} else {
right -= 1;
}
}
None
}
fn main() {
println!("Optimized Two Sum II tests");
println!("{:?}", two_sum_two_pointers(&[2, 7, 11, 15], 9)); // Some((1,2))
println!("{:?}", two_sum_two_pointers(&[2, 3, 4], 6)); // Some((1,3))
println!("{:?}", two_sum_two_pointers(&[-1, 0], -1)); // Some((1,2))
}
/*
COMMENTS — Optimized (Rust)
Why this solution:
- Uses sorted property to find target pair in linear time.
Complexity:
- Time: O(n), Space: O(1)
Interview tips:
- Discuss safety of indexing and conversion between signed/unsigned indices carefully in Rust.
- Explain pointer invariant and 1-based return requirement for LC167.
*/
<?php
function twoSumBrute(array $numbers, int $target): array {
$n = count($numbers);
for ($i = 0; $i < $n - 1; $i++) {
for ($j = $i + 1; $j < $n; $j++) {
if ($numbers[$i] + $numbers[$j] === $target) {
return [$i + 1, $j + 1];
}
}
}
return [];
}
if (realpath(__FILE__) === realpath($_SERVER['SCRIPT_FILENAME'])) {
echo "Brute-force Two Sum II tests\n";
print_r(twoSumBrute([2,7,11,15], 9));
print_r(twoSumBrute([2,3,4], 6));
print_r(twoSumBrute([-1,0], -1));
}
?>
<?php
// File: php.brute.php
// Problem: Two Sum II - Input array is sorted (LeetCode 167)
// Approach: Brute-force nested loops (O(n^2))
// Returns 1-based indices per LeetCode requirement
function twoSumBrute(array $numbers, int $target): array {
$n = count($numbers);
for ($i = 0; $i < $n - 1; $i++) {
for ($j = $i + 1; $j < $n; $j++) {
if ($numbers[$i] + $numbers[$j] === $target) {
// Return 1-based indices
return [$i + 1, $j + 1];
}
}
}
return [];
}
// Quick tests for local verification
if (realpath(__FILE__) === realpath($_SERVER['SCRIPT_FILENAME'])) {
echo "Brute-force Two Sum II tests\n";
print_r(twoSumBrute([2,7,11,15], 9)); // [1,2]
print_r(twoSumBrute([2,3,4], 6)); // [1,3]
print_r(twoSumBrute([-1,0], -1)); // [1,2]
}
/*
COMMENTS — Brute (PHP)
Why this solution:
- Simple to reason about; good baseline to explain correctness.
Complexity:
- Time: O(n^2)
- Space: O(1) auxiliary
Interview notes:
- After explaining brute-force, present optimized two-pointer solution for sorted arrays.
*/
?>
<?php
function twoSumTwoPointers(array $numbers, int $target): array {
$left = 0;
$right = count($numbers) - 1;
while ($left < $right) {
$sum = $numbers[$left] + $numbers[$right];
if ($sum === $target) {
return [$left + 1, $right + 1];
}
if ($sum < $target) {
$left++;
} else {
$right--;
}
}
return [];
}
if (realpath(__FILE__) === realpath($_SERVER['SCRIPT_FILENAME'])) {
echo "Optimized Two Sum II tests\n";
print_r(twoSumTwoPointers([2,7,11,15], 9));
print_r(twoSumTwoPointers([2,3,4], 6));
print_r(twoSumTwoPointers([-1,0], -1));
}
?>
<?php
// File: php.optimized.php
// Problem: Two Sum II - Input array is sorted (LeetCode 167)
// Approach: Two-pointer (left/right) — O(n) time, O(1) space
function twoSumTwoPointers(array $numbers, int $target): array {
$left = 0;
$right = count($numbers) - 1;
while ($left < $right) {
$sum = $numbers[$left] + $numbers[$right];
if ($sum === $target) {
return [$left + 1, $right + 1]; // 1-based
}
if ($sum < $target) {
$left++;
} else {
$right--;
}
}
return [];
}
// Quick tests for local verification
if (realpath(__FILE__) === realpath($_SERVER['SCRIPT_FILENAME'])) {
echo "Optimized Two Sum II tests\n";
print_r(twoSumTwoPointers([2,7,11,15], 9)); // [1,2]
print_r(twoSumTwoPointers([2,3,4], 6)); // [1,3]
print_r(twoSumTwoPointers([-1,0], -1)); // [1,2]
}
/*
COMMENTS — Optimized (PHP)
Why this solution:
- Leverages sorted property to locate pair in linear time with two pointers.
Complexity:
- Time: O(n), Space: O(1)
Interview tips:
- Explain pointer invariant and 1-based index return requirement for LeetCode 167.
*/
?>
List<int> twoSumBrute(List<int> numbers, int target) {
int n = numbers.length;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (numbers[i] + numbers[j] == target) {
return [i + 1, j + 1];
}
}
}
return [];
}
void main() {
print('Brute-force Two Sum II tests');
print(twoSumBrute([2, 7, 11, 15], 9));
print(twoSumBrute([2, 3, 4], 6));
print(twoSumBrute([-1, 0], -1));
}
// File: dart.brute.dart
// Problem: Two Sum II - Input array is sorted (LeetCode 167)
// Approach: Brute-force nested loops (O(n^2))
// Returns 1-based positions as required by LeetCode 167
List<int> twoSumBrute(List<int> numbers, int target) {
int n = numbers.length;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (numbers[i] + numbers[j] == target) {
// Return 1-based indices
return [i + 1, j + 1];
}
}
}
return [];
}
void main() {
print('Brute-force Two Sum II tests');
print(twoSumBrute([2, 7, 11, 15], 9)); // [1,2]
print(twoSumBrute([2, 3, 4], 6)); // [1,3]
print(twoSumBrute([-1, 0], -1)); // [1,2]
}
/*
COMMENTS — Brute (Dart)
Why this solution:
- Straightforward baseline to show correctness by checking all pairs.
Interview tips:
- Present brute-force first to show correctness, then explain optimized two-pointer approach.
Complexity:
- Time: O(n^2)
- Space: O(1) auxiliary
*/
List<int> twoSumTwoPointers(List<int> numbers, int target) {
int left = 0;
int right = numbers.length - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
return [left + 1, right + 1];
}
if (sum < target) {
left++;
} else {
right--;
}
}
return [];
}
void main() {
print('Optimized Two Sum II tests');
print(twoSumTwoPointers([2, 7, 11, 15], 9));
print(twoSumTwoPointers([2, 3, 4], 6));
print(twoSumTwoPointers([-1, 0], -1));
}
// File: dart.optimized.dart
// Problem: Two Sum II - Input array is sorted (LeetCode 167)
// Approach: Two-pointer (left/right) — O(n) time, O(1) space
List<int> twoSumTwoPointers(List<int> numbers, int target) {
int left = 0;
int right = numbers.length - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
return [left + 1, right + 1]; // 1-based
}
if (sum < target) {
left++;
} else {
right--;
}
}
return [];
}
void main() {
print('Optimized Two Sum II tests');
print(twoSumTwoPointers([2, 7, 11, 15], 9)); // [1,2]
print(twoSumTwoPointers([2, 3, 4], 6)); // [1,3]
print(twoSumTwoPointers([-1, 0], -1)); // [1,2]
}
/*
COMMENTS — Optimized (Dart)
Why this solution:
- Uses sorted property to find pair in linear time using two pointers.
Complexity:
- Time: O(n), Space: O(1)
Interview notes:
- Explain pointer invariant and 1-based index requirement for LeetCode 167.
*/
