function twoSumBrute(nums, target) {
const n = nums.length;
for (let i = 0; i < n - 1; i++) {
for (let j = i + 1; j < n; j++) {
if (nums[i] + nums[j] === target) {
return [i, j];
}
}
}
return [];
}
if (require && require.main === module) {
console.log('Brute tests');
console.log(twoSumBrute([2,7,11,15], 9));
console.log(twoSumBrute([3,2,4], 6));
console.log(twoSumBrute([3,3], 6));
console.log(twoSumBrute([1,2,3], 7));
}
// File: javascript.brute.js
// Brute-force Two Sum
// O(n^2) time, O(1) extra space
/**
* Brute-force implementation of Two Sum.
* Tries all pairs (i, j), i < j, and returns first matching pair of indices.
* This is useful to demonstrate correctness as a baseline in interviews.
*
* @param {number[]} nums - input array of integers
* @param {number} target - target sum
* @returns {number[]} pair of indices [i, j] or [] if none
*/
function twoSumBrute(nums, target) {
const n = nums.length;
for (let i = 0; i < n - 1; i++) {
for (let j = i + 1; j < n; j++) {
if (nums[i] + nums[j] === target) {
return [i, j];
}
}
}
return [];
}
// Simple runner + edge-case tests for local execution
if (require && require.main === module) {
console.log('Brute tests');
console.log(twoSumBrute([2,7,11,15], 9)); // [0,1]
console.log(twoSumBrute([3,2,4], 6)); // [1,2]
console.log(twoSumBrute([3,3], 6)); // [0,1]
console.log(twoSumBrute([1,2,3], 7)); // []
}
/*
COMMENTS — Brute
Why this solution:
- Simple to write and reason about; demonstrates correctness by exhaustive search.
Where to use:
- As a first demonstration in interviews, on tiny inputs, or when n is guaranteed small.
Keywords to spot this approach in problem statements:
- "check all pairs", "combination of two elements", or when n is tiny (e.g., n <= 100)
Complexity:
- Time: O(n^2) because it checks all i<j pairs (about n*(n-1)/2 checks).
- Space: O(1) extra (only indices and loop counters). Note: returning results doesn't count as extra space.
*/
function twoSumOptimized(nums, target) {
const seen = new Map();
for (let i = 0; i < nums.length; i++) {
const x = nums[i];
const complement = target - x;
if (seen.has(complement)) {
return [seen.get(complement), i];
}
seen.set(x, i);
}
return [];
}
if (require && require.main === module) {
console.log('\nOptimized tests');
console.log(twoSumOptimized([2,7,11,15], 9));
console.log(twoSumOptimized([3,2,4], 6));
console.log(twoSumOptimized([3,3], 6));
console.log(twoSumOptimized([0,4,3,0], 0));
console.log(twoSumOptimized([], 0));
}
module.exports = {
twoSumBrute,
twoSumOptimized
};
// File: javascript.optimized.js
// One-pass hash map Two Sum
// O(n) time average, O(n) space
/**
* Optimized Two Sum using a hash map. For each element x at index i we check
* if (target - x) has been seen earlier. If yes, return the earlier index and i.
* We check complement before inserting current value to avoid self-matching and
* to handle duplicates correctly.
*
* @param {number[]} nums
* @param {number} target
* @returns {number[]} pair of indices [i, j] or []
*/
function twoSumOptimized(nums, target) {
const seen = new Map(); // value -> index
for (let i = 0; i < nums.length; i++) {
const x = nums[i];
const complement = target - x;
if (seen.has(complement)) {
return [seen.get(complement), i];
}
// store current value for future complements
seen.set(x, i);
}
return [];
}
// Runner & tests when executed directly
if (require && require.main === module) {
console.log('\nOptimized tests');
console.log(twoSumOptimized([2,7,11,15], 9)); // [0,1]
console.log(twoSumOptimized([3,2,4], 6)); // [1,2]
console.log(twoSumOptimized([3,3], 6)); // [0,1]
console.log(twoSumOptimized([0,4,3,0], 0)); // [0,3]
console.log(twoSumOptimized([], 0)); // []
}
/*
COMMENTS — Optimized
Why this solution:
- Uses a hash map for average O(1) lookup of complements, enabling an overall O(n) one-pass solution.
Where to use:
- Default interview solution when indices must be returned and array is unsorted.
Keywords to spot this approach in problem statements:
- "two numbers", "pair", "return indices", "sum equals target", "unsorted array".
Complexity:
- Time: O(n) average. Each element is visited once; map lookups/inserts are O(1) on average. In adversarial worst-cases
a hash map can degrade, but this is rare and acceptable in interviews.
- Space: O(n) extra for the hash map storing seen values -> indices. The map size grows until a match is found or all
elements are processed.
Additional notes to say in interview:
- Always check complement before inserting current element to avoid matching element with itself (e.g., x+x==target).
- If input is sorted or indices are not required, a sort+two-pointer approach may be preferred to reduce space, at
the cost of O(n log n) time.
*/
// Export functions for test runners
module.exports = {
twoSumBrute,
twoSumOptimized
};
def two_sum_brute(nums, target):
n = len(nums)
for i in range(n-1):
for j in range(i+1, n):
if nums[i] + nums[j] == target:
return [i, j]
return []
# File: python.brute.py
# Brute-force Two Sum (Python)
# Time: O(n^2), Space: O(1)
def two_sum_brute(nums, target):
n = len(nums)
for i in range(n-1):
for j in range(i+1, n):
if nums[i] + nums[j] == target:
return [i, j]
return []
def two_sum_optimized(nums, target):
seen = {}
for i, x in enumerate(nums):
c = target - x
if c in seen:
return [seen[c], i]
seen[x] = i
return []
if __name__ == '__main__':
print(two_sum_brute([2,7,11,15], 9))
print(two_sum_optimized([2,7,11,15], 9))
print(two_sum_optimized([3,3], 6))
'''
Comments (Python)
Why this solution:
- The hashmap approach is concise in Python and uses dict for O(1) lookups.
Where to use:
- Default interview variant. Python dict is convenient for concise answers.
Complexity:
- Time: O(n) average. Space: O(n).
Keywords:
- "two numbers", "pair", "target", "return indices".
'''
# File: python.optimized.py
# One-pass hashmap Two Sum (Python)
# Time: O(n) average, Space: O(n)
def two_sum_optimized(nums, target):
seen = {}
for i, x in enumerate(nums):
c = target - x
if c in seen:
return [seen[c], i]
seen[x] = i
return []
# Runner tests
if __name__ == '__main__':
print(two_sum_brute([2,7,11,15], 9)) # [0,1]
print(two_sum_optimized([2,7,11,15], 9)) # [0,1]
print(two_sum_optimized([3,3], 6)) # [0,1]
'''
Comments (Python)
Why this solution:
- The hashmap approach is concise in Python and uses dict for O(1) lookups.
Where to use:
- Default interview variant. Python dict is convenient for concise answers.
Complexity:
- Time: O(n) average. Space: O(n).
Keywords:
- "two numbers", "pair", "target", "return indices".
'''
public class SolutionBrute {
public static int[] twoSumBrute(int[] nums, int target) {
int n = nums.length;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (nums[i] + nums[j] == target) return new int[]{i, j};
}
}
return new int[0];
}
public static void main(String[] args) {
int[] nums = {2,7,11,15};
int[] r = twoSumBrute(nums, 9);
System.out.println(r[0] + "," + r[1]);
}
}
// File: java.brute.java
// Brute-force Two Sum (Java)
// Time: O(n^2), Space: O(1)
public class SolutionBrute {
public static int[] twoSumBrute(int[] nums, int target) {
int n = nums.length;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (nums[i] + nums[j] == target) return new int[]{i, j};
}
}
return new int[0];
}
// simple runner
public static void main(String[] args) {
int[] nums = {2,7,11,15};
int[] r = twoSumBrute(nums, 9);
System.out.println(r[0] + "," + r[1]);
}
}
import java.util.HashMap;
public class Solution {
public static int[] twoSumOptimized(int[] nums, int target) {
HashMap<Integer, Integer> seen = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int x = nums[i];
int c = target - x;
if (seen.containsKey(c)) return new int[]{seen.get(c), i};
seen.put(x, i);
}
return new int[0];
}
public static void main(String[] args) {
int[] nums = {2,7,11,15};
int[] r = twoSumOptimized(nums, 9);
System.out.println(r[0] + "," + r[1]);
}
}
// File: java.optimized.java
// One-pass HashMap Two Sum (Java)
// Time: O(n) average, Space: O(n)
import java.util.HashMap;
public class Solution {
public static int[] twoSumOptimized(int[] nums, int target) {
HashMap<Integer, Integer> seen = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int x = nums[i];
int c = target - x;
if (seen.containsKey(c)) return new int[]{seen.get(c), i};
seen.put(x, i);
}
return new int[0];
}
public static void main(String[] args) {
int[] nums = {2,7,11,15};
int[] r = twoSumOptimized(nums, 9);
System.out.println(r[0] + "," + r[1]);
}
}
/*
Comments (Java)
Why this solution:
- HashMap provides O(1) average lookup for complements.
Where to use:
- Typical interview variant when indices must be returned.
Keywords to spot:
- "return indices", "pair sum", "two numbers".
Complexity:
- Time: O(n) average (single pass). Each put/containsKey is O(1) average.
- Space: O(n) for HashMap.
*/
#include <vector>
#include <iostream>
using namespace std;
vector<int> twoSumBrute(const vector<int>& nums, int target) {
int n = nums.size();
for (int i = 0; i < n - 1; ++i) {
for (int j = i + 1; j < n; ++j) {
if (nums[i] + nums[j] == target) return {i, j};
}
}
return {};
}
// File: cpp.brute.cpp
// Brute-force Two Sum (C++)
// Time: O(n^2), Space: O(1)
#include <vector>
#include <iostream>
using namespace std;
vector<int> twoSumBrute(const vector<int>& nums, int target) {
int n = nums.size();
for (int i = 0; i < n - 1; ++i) {
for (int j = i + 1; j < n; ++j) {
if (nums[i] + nums[j] == target) return {i, j};
}
}
return {};
}
#include <unordered_map>
vector<int> twoSumOptimized(const vector<int>& nums, int target) {
unordered_map<int,int> seen;
for (int i = 0; i < (int)nums.size(); ++i) {
int x = nums[i];
int c = target - x;
auto it = seen.find(c);
if (it != seen.end()) return {it->second, i};
seen[x] = i;
}
return {};
}
int main() {
vector<int> a = {2,7,11,15};
auto res1 = twoSumBrute(a, 9);
cout << res1[0] << "," << res1[1] << "\n";
auto res2 = twoSumOptimized(a, 9);
cout << res2[0] << "," << res2[1] << "\n";
vector<int> b = {3,3};
auto r3 = twoSumOptimized(b, 6);
cout << r3[0] << "," << r3[1] << "\n";
return 0;
}
// File: cpp.optimized.cpp
// One-pass hash map Two Sum (C++)
// Time: O(n) average, Space: O(n)
#include <unordered_map>
vector<int> twoSumOptimized(const vector<int>& nums, int target) {
unordered_map<int,int> seen; // value -> index
for (int i = 0; i < (int)nums.size(); ++i) {
int x = nums[i];
int c = target - x;
auto it = seen.find(c);
if (it != seen.end()) return {it->second, i};
seen[x] = i;
}
return {};
}
// Runner / main for local testing
int main() {
vector<int> a = {2,7,11,15};
auto res1 = twoSumBrute(a, 9);
cout << res1[0] << "," << res1[1] << "\n"; // 0,1
auto res2 = twoSumOptimized(a, 9);
cout << res2[0] << "," << res2[1] << "\n"; // 0,1
// Edge-case tests
vector<int> b = {3,3};
auto r3 = twoSumOptimized(b, 6);
cout << r3[0] << "," << r3[1] << "\n"; // 0,1
return 0;
}
/*
Comments (C++)
Why this solution:
- Brute: simplest correct approach; good to explain baseline during interviews.
- Optimized: uses unordered_map for O(1) average lookup of complements.
Where to use:
- Use optimized for typical interview constraints (large n, unsorted array, indices required).
Keywords to spot problem:
- "two numbers", "pair", "sum to target", "return indices", "unsorted array".
Complexity explanation:
- Brute: O(n^2) because every pair (i,j) is checked.
- Optimized: O(n) average because each element is inserted/queried in the hash table once; space O(n) to store seen values.
*/
using System;
public class SolutionBrute {
public static int[] TwoSumBrute(int[] nums, int target) {
int n = nums.Length;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (nums[i] + nums[j] == target) return new int[]{i, j};
}
}
return new int[0];
}
public static void Main() {
var r = TwoSumBrute(new int[]{2,7,11,15}, 9);
Console.WriteLine($"{r[0]},{r[1]}");
}
}
// File: csharp.brute.cs
// Brute-force Two Sum (C#)
// Time: O(n^2), Space: O(1)
using System;
public class SolutionBrute {
public static int[] TwoSumBrute(int[] nums, int target) {
int n = nums.Length;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (nums[i] + nums[j] == target) return new int[]{i, j};
}
}
return new int[0];
}
public static void Main() {
var r = TwoSumBrute(new int[]{2,7,11,15}, 9);
Console.WriteLine($"{r[0]},{r[1]}");
}
}
using System;
using System.Collections.Generic;
public class Solution {
public static int[] TwoSumOptimized(int[] nums, int target) {
var seen = new Dictionary<int,int>();
for (int i = 0; i < nums.Length; i++) {
int x = nums[i];
int c = target - x;
if (seen.ContainsKey(c)) return new int[]{seen[c], i};
seen[x] = i;
}
return new int[0];
}
public static void Main() {
var r = TwoSumOptimized(new int[]{2,7,11,15}, 9);
Console.WriteLine($"{r[0]},{r[1]}");
}
}
// File: csharp.optimized.cs
// One-pass Dictionary Two Sum (C#)
// Time: O(n) average, Space: O(n)
using System;
using System.Collections.Generic;
public class Solution {
public static int[] TwoSumOptimized(int[] nums, int target) {
var seen = new Dictionary<int,int>();
for (int i = 0; i < nums.Length; i++) {
int x = nums[i];
int c = target - x;
if (seen.ContainsKey(c)) return new int[]{seen[c], i};
seen[x] = i;
}
return new int[0];
}
public static void Main() {
var r = TwoSumOptimized(new int[]{2,7,11,15}, 9);
Console.WriteLine($"{r[0]},{r[1]}");
}
}
/*
C# Comments
- Similar to Java: Dictionary provides average O(1) lookups.
- Mention checking complement before insert in interview to avoid self-match.
*/
package main
import "fmt"
func twoSumBruteGo(nums []int, target int) []int {
n := len(nums)
for i := 0; i < n-1; i++ {
for j := i+1; j < n; j++ {
if nums[i] + nums[j] == target {
return []int{i, j}
}
}
}
return []int{}
}
// File: go.brute.go
// Brute-force Two Sum (Go)
// Time: O(n^2), Space: O(1)
package main
import "fmt"
func twoSumBruteGo(nums []int, target int) []int {
n := len(nums)
for i := 0; i < n-1; i++ {
for j := i+1; j < n; j++ {
if nums[i] + nums[j] == target {
return []int{i, j}
}
}
}
return []int{}
}
func twoSumOptimizedGo(nums []int, target int) []int {
seen := make(map[int]int)
for i, x := range nums {
c := target - x
if j, ok := seen[c]; ok {
return []int{j, i}
}
seen[x] = i
}
return []int{}
}
func main() {
fmt.Println(twoSumBruteGo([]int{2,7,11,15}, 9))
fmt.Println(twoSumOptimizedGo([]int{2,7,11,15}, 9))
}
// File: go.optimized.go
// One-pass map Two Sum (Go)
// Time: O(n) average, Space: O(n)
func twoSumOptimizedGo(nums []int, target int) []int {
seen := make(map[int]int)
for i, x := range nums {
c := target - x
if j, ok := seen[c]; ok {
return []int{j, i}
}
seen[x] = i
}
return []int{}
}
func main() {
fmt.Println(twoSumBruteGo([]int{2,7,11,15}, 9)) // [0 1]
fmt.Println(twoSumOptimizedGo([]int{2,7,11,15}, 9)) // [0 1]
}
/*
Comments (Go)
- Use map[int]int for seen values.
- Complexity: O(n) time average, O(n) space.
*/
export function twoSumBruteTS(nums: number[], target: number): number[] {
for (let i = 0; i < nums.length - 1; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] === target) return [i, j];
}
}
return [];
}
// File: typescript.brute.ts
// Brute-force Two Sum (TypeScript)
// Time: O(n^2), Space: O(1)
export function twoSumBruteTS(nums: number[], target: number): number[] {
for (let i = 0; i < nums.length - 1; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] === target) return [i, j];
}
}
return [];
}
export function twoSumOptimizedTS(nums: number[], target: number): number[] {
const seen = new Map<number, number>();
for (let i = 0; i < nums.length; i++) {
const x = nums[i];
const c = target - x;
if (seen.has(c)) return [seen.get(c)!, i];
seen.set(x, i);
}
return [];
}
// File: typescript.optimized.ts
// One-pass Map Two Sum (TypeScript)
// Time: O(n) average, Space: O(n)
export function twoSumOptimizedTS(nums: number[], target: number): number[] {
const seen = new Map<number, number>();
for (let i = 0; i < nums.length; i++) {
const x = nums[i];
const c = target - x;
if (seen.has(c)) return [seen.get(c)!, i];
seen.set(x, i);
}
return [];
}
// Runner (uncomment to test in Node with ts-node)
// console.log(twoSumOptimizedTS([2,7,11,15], 9));
/*
Comments (TypeScript)
- Same reasoning as JavaScript. Use Map<number,number> for clarity.
- Complexity: O(n) average time, O(n) space.
*/
def two_sum_brute_ruby(nums, target)
(0...nums.length-1).each do |i|
(i+1...nums.length).each do |j|
return [i, j] if nums[i] + nums[j] == target
end
end
[]
end
# File: ruby.brute.rb
# Brute-force Two Sum (Ruby)
# Time: O(n^2), Space: O(1)
def two_sum_brute_ruby(nums, target)
(0...nums.length-1).each do |i|
(i+1...nums.length).each do |j|
return [i, j] if nums[i] + nums[j] == target
end
end
[]
end
def two_sum_optimized_ruby(nums, target)
seen = {}
nums.each_with_index do |x, i|
c = target - x
return [seen[c], i] if seen.key?(c)
seen[x] = i
end
[]
end
if __FILE__ == $0
p two_sum_brute_ruby([2,7,11,15], 9)
p two_sum_optimized_ruby([2,7,11,15], 9)
end
# File: ruby.optimized.rb
# One-pass hash Two Sum (Ruby)
# Time: O(n) average, Space: O(n)
def two_sum_optimized_ruby(nums, target)
seen = {}
nums.each_with_index do |x, i|
c = target - x
return [seen[c], i] if seen.key?(c)
seen[x] = i
end
[]
end
# Runner
if __FILE__ == $0
p two_sum_brute_ruby([2,7,11,15], 9)
p two_sum_optimized_ruby([2,7,11,15], 9)
end
=begin
Comments (Ruby)
- Use Hash for seen values.
- Complexity: O(n) time average, O(n) space.
=end
import Foundation
func twoSumBruteSwift(_ nums: [Int], _ target: Int) -> [Int] {
let n = nums.count
for i in 0..<(n-1) {
for j in (i+1)..<n {
if nums[i] + nums[j] == target { return [i, j] }
}
}
return []
}
// File: swift.brute.swift
// Brute-force Two Sum (Swift)
// Time: O(n^2), Space: O(1)
import Foundation
func twoSumBruteSwift(_ nums: [Int], _ target: Int) -> [Int] {
let n = nums.count
for i in 0..<(n-1) {
for j in (i+1)..<n {
if nums[i] + nums[j] == target { return [i, j] }
}
}
return []
}
func twoSumOptimizedSwift(_ nums: [Int], _ target: Int) -> [Int] {
var seen = [Int:Int]()
for (i, x) in nums.enumerated() {
let c = target - x
if let j = seen[c] { return [j, i] }
seen[x] = i
}
return []
}
print(twoSumBruteSwift([2,7,11,15], 9))
print(twoSumOptimizedSwift([2,7,11,15], 9))
// File: swift.optimized.swift
// One-pass dict Two Sum (Swift)
// Time: O(n) average, Space: O(n)
func twoSumOptimizedSwift(_ nums: [Int], _ target: Int) -> [Int] {
var seen = [Int:Int]()
for (i, x) in nums.enumerated() {
let c = target - x
if let j = seen[c] { return [j, i] }
seen[x] = i
}
return []
}
// Runner
print(twoSumBruteSwift([2,7,11,15], 9))
print(twoSumOptimizedSwift([2,7,11,15], 9))
/*
Comments (Swift)
- Use Dictionary for hashmap behavior.
- Complexity: O(n) average, O(n) space.
*/
fun twoSumBruteKotlin(nums: IntArray, target: Int): IntArray {
for (i in 0 until nums.size - 1) {
for (j in i+1 until nums.size) {
if (nums[i] + nums[j] == target) return intArrayOf(i, j)
}
}
return intArrayOf()
}
// File: kotlin.brute.kt
// Brute-force Two Sum (Kotlin)
// Time: O(n^2), Space: O(1)
fun twoSumBruteKotlin(nums: IntArray, target: Int): IntArray {
for (i in 0 until nums.size - 1) {
for (j in i+1 until nums.size) {
if (nums[i] + nums[j] == target) return intArrayOf(i, j)
}
}
return intArrayOf()
}
fun twoSumOptimizedKotlin(nums: IntArray, target: Int): IntArray {
val seen = HashMap<Int, Int>()
for (i in nums.indices) {
val x = nums[i]
val c = target - x
if (seen.containsKey(c)) return intArrayOf(seen[c]!!, i)
seen[x] = i
}
return intArrayOf()
}
fun main() {
println(twoSumOptimizedKotlin(intArrayOf(2,7,11,15), 9).joinToString())
}
// File: kotlin.optimized.kt
// One-pass HashMap Two Sum (Kotlin)
// Time: O(n) average, Space: O(n)
fun twoSumOptimizedKotlin(nums: IntArray, target: Int): IntArray {
val seen = HashMap<Int, Int>()
for (i in nums.indices) {
val x = nums[i]
val c = target - x
if (seen.containsKey(c)) return intArrayOf(seen[c]!!, i)
seen[x] = i
}
return intArrayOf()
}
fun main() {
println(twoSumOptimizedKotlin(intArrayOf(2,7,11,15), 9).joinToString()) // 0, 1
}
/*
Comments (Kotlin)
- Similar approach to Java; use HashMap for seen values.
- Complexity: O(n) time average, O(n) space.
*/
object TwoSumBrute {
def twoSum(nums: Array[Int], target: Int): Array[Int] = {
for (i <- 0 until nums.length - 1) {
for (j <- i+1 until nums.length) {
if (nums(i) + nums(j) == target) return Array(i, j)
}
}
Array()
}
}
// File: scala.brute.scala
// Brute-force Two Sum (Scala)
// Time: O(n^2), Space: O(1)
object TwoSumBrute {
def twoSum(nums: Array[Int], target: Int): Array[Int] = {
for (i <- 0 until nums.length - 1) {
for (j <- i+1 until nums.length) {
if (nums(i) + nums(j) == target) return Array(i, j)
}
}
Array()
}
}
object TwoSumOptimized {
def twoSum(nums: Array[Int], target: Int): Array[Int] = {
val seen = scala.collection.mutable.Map[Int, Int]()
for (i <- nums.indices) {
val x = nums(i)
val c = target - x
if (seen.contains(c)) return Array(seen(c), i)
seen(x) = i
}
Array()
}
def main(args: Array[String]): Unit = {
val res = twoSum(Array(2,7,11,15), 9)
println(res.mkString(","))
}
}
// File: scala.optimized.scala
// Optimized Two Sum (Scala)
// Time: O(n) average, Space: O(n)
object TwoSumOptimized {
def twoSum(nums: Array[Int], target: Int): Array[Int] = {
val seen = scala.collection.mutable.Map[Int, Int]()
for (i <- nums.indices) {
val x = nums(i)
val c = target - x
if (seen.contains(c)) return Array(seen(c), i)
seen(x) = i
}
Array()
}
def main(args: Array[String]): Unit = {
val res = twoSum(Array(2,7,11,15), 9)
println(res.mkString(","))
}
}
/*
Comments (Scala)
- Use mutable Map for seen values.
- Complexity: O(n) average, O(n) space.
*/
pub fn two_sum_brute_rust(nums: Vec<i32>, target: i32) -> Vec<i32> {
for i in 0..nums.len()-1 {
for j in i+1..nums.len() {
if nums[i] + nums[j] == target { return vec![i as i32, j as i32]; }
}
}
vec![]
}
// File: rust.brute.rs
// Brute-force Two Sum (Rust)
// Time: O(n^2), Space: O(1)
pub fn two_sum_brute_rust(nums: Vec<i32>, target: i32) -> Vec<i32> {
for i in 0..nums.len()-1 {
for j in i+1..nums.len() {
if nums[i] + nums[j] == target { return vec![i as i32, j as i32]; }
}
}
vec![]
}
use std::collections::HashMap;
pub fn two_sum_optimized_rust(nums: Vec<i32>, target: i32) -> Vec<i32> {
let mut seen: HashMap<i32, usize> = HashMap::new();
for (i, &x) in nums.iter().enumerate() {
let c = target - x;
if let Some(&j) = seen.get(&c) { return vec![j as i32, i as i32]; }
seen.insert(x, i);
}
vec![]
}
// File: rust.optimized.rs
// One-pass HashMap Two Sum (Rust)
// Time: O(n) average, Space: O(n)
use std::collections::HashMap;
pub fn two_sum_optimized_rust(nums: Vec<i32>, target: i32) -> Vec<i32> {
let mut seen: HashMap<i32, usize> = HashMap::new();
for (i, &x) in nums.iter().enumerate() {
let c = target - x;
if let Some(&j) = seen.get(&c) { return vec![j as i32, i as i32]; }
seen.insert(x, i);
}
vec![]
}
// Runner (example) - uncomment to run in main
// fn main() {
// println!("{:?}", two_sum_optimized_rust(vec![2,7,11,15], 9));
// }
/*
Comments (Rust)
- Use HashMap<i32, usize> for seen table.
- Complexity: O(n) average, O(n) space.
*/
<?php
function twoSumBrutePHP($nums, $target) {
$n = count($nums);
for ($i = 0; $i < $n - 1; $i++) {
for ($j = $i + 1; $j < $n; $j++) {
if ($nums[$i] + $nums[$j] == $target) return [$i, $j];
}
}
return [];
}
<?php
// File: php.brute.php
// Brute-force Two Sum (PHP)
// Time: O(n^2), Space: O(1)
function twoSumBrutePHP($nums, $target) {
$n = count($nums);
for ($i = 0; $i < $n - 1; $i++) {
for ($j = $i + 1; $j < $n; $j++) {
if ($nums[$i] + $nums[$j] == $target) return [$i, $j];
}
}
return [];
}
function twoSumOptimizedPHP($nums, $target) {
$seen = array();
for ($i = 0; $i < count($nums); $i++) {
$x = $nums[$i];
$c = $target - $x;
if (array_key_exists($c, $seen)) return [$seen[$c], $i];
$seen[$x] = $i;
}
return [];
}
print_r(twoSumBrutePHP([2,7,11,15], 9));
print_r(twoSumOptimizedPHP([2,7,11,15], 9));
?>
// File: php.optimized.php
// One-pass associative array Two Sum (PHP)
// Time: O(n) average, Space: O(n)
function twoSumOptimizedPHP($nums, $target) {
$seen = array();
for ($i = 0; $i < count($nums); $i++) {
$x = $nums[$i];
$c = $target - $x;
if (array_key_exists($c, $seen)) return [$seen[$c], $i];
$seen[$x] = $i;
}
return [];
}
// Runner
print_r(twoSumBrutePHP([2,7,11,15], 9));
print_r(twoSumOptimizedPHP([2,7,11,15], 9));
/*
Comments (PHP)
- Use associative arrays for hash map behavior.
- Complexity: O(n) average, O(n) space.
*/
?>
List<int> twoSumBruteDart(List<int> nums, int target) {
for (var i = 0; i < nums.length - 1; i++) {
for (var j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) return [i, j];
}
}
return [];
}
// File: dart.brute.dart
// Brute-force Two Sum (Dart)
// Time: O(n^2), Space: O(1)
List<int> twoSumBruteDart(List<int> nums, int target) {
for (var i = 0; i < nums.length - 1; i++) {
for (var j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) return [i, j];
}
}
return [];
}
List<int> twoSumOptimizedDart(List<int> nums, int target) {
final seen = <int,int>{};
for (var i = 0; i < nums.length; i++) {
final x = nums[i];
final c = target - x;
if (seen.containsKey(c)) return [seen[c]!, i];
seen[x] = i;
}
return [];
}
void main() {
print(twoSumBruteDart([2,7,11,15], 9));
print(twoSumOptimizedDart([2,7,11,15], 9));
}
// File: dart.optimized.dart
// One-pass Two Sum (Dart)
// Time: O(n) average, Space: O(n)
List<int> twoSumOptimizedDart(List<int> nums, int target) {
final seen = <int,int>{};
for (var i = 0; i < nums.length; i++) {
final x = nums[i];
final c = target - x;
if (seen.containsKey(c)) return [seen[c]!, i];
seen[x] = i;
}
return [];
}
void main() {
print(twoSumBruteDart([2,7,11,15], 9));
print(twoSumOptimizedDart([2,7,11,15], 9));
}
/*
Comments (Dart)
- Map<int,int> used for seen values.
- Complexity: O(n) average, O(n) space.
*/
