Skip to content

Commit 21a12ca

Browse files
Gabb-cGabb-c
committed
chore: refactor two sum
1 parent 7260957 commit 21a12ca

File tree

20 files changed

+139
-63
lines changed

20 files changed

+139
-63
lines changed

‎.lintstagedrc.js‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2,5 +2,5 @@ export default {
22
"*.{js,ts,cjs,mjs,d.cts,d.mts,jsx,tsx,json,jsonc}": [
33
"biome check --apply-unsafe --no-errors-on-unmatched",
44
],
5-
"*.{js,ts}": "vitest related --run",
5+
"*.ts": ["vitest related --run"],
66
};

‎package.json‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -18,8 +18,8 @@
1818
"license": "ISC",
1919
"devDependencies": {
2020
"@biomejs/biome": "^1.6.4",
21-
"@commitlint/cli": "^19.2.1",
22-
"@commitlint/config-conventional": "^19.1.0",
21+
"@commitlint/cli": "^19.2.2",
22+
"@commitlint/config-conventional": "^19.2.2",
2323
"@types/node": "^20.12.7",
2424
"@vitest/coverage-v8": "^1.5.0",
2525
"@vitest/ui": "^1.5.0",

‎pnpm-lock.yaml‎

Lines changed: 20 additions & 14 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎src/arrays/1-two-sum/index.ts‎

Lines changed: 40 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,7 @@
1+
import type { LeetcodeProblem } from "shared/typings/leetcode-problem";
2+
13
/**
24
* Finds the indices of two numbers in an array that add up to a target sum.
3-
* (This problem can be found on LeetCode: https://leetcode.com/problems/two-sum/)
45
*
56
* @param {number[]} nums - The array of numbers to search.
67
* @param {number} target - The target sum.
@@ -9,7 +10,7 @@
910
* @timeComplexity O(n) - Linear time complexity due to the single pass through the array.
1011
* @spaceComplexity O(n) - Uses a Map to store seen numbers, which scales linearly with the input size.
1112
*/
12-
export const twoSum = (nums: number[], target: number): number[] => {
13+
const hashMap = (nums: number[], target: number): number[] => {
1314
// Create a Map to store numbers and their corresponding indices.
1415
const numIndicesMap = new Map<number, number>();
1516

@@ -30,3 +31,40 @@ export const twoSum = (nums: number[], target: number): number[] => {
3031
// If no pair is found, return an empty array.
3132
return [];
3233
};
34+
35+
/**
36+
* Finds the indices of two numbers in an array that add up to a target sum using brute force.
37+
*
38+
* @param {number[]} nums - The array of numbers to search.
39+
* @param {number} target - The target sum.
40+
* @returns {number[]} An array containing the indices of the two numbers that add up to the target sum, or an empty array if no such pair exists.
41+
*
42+
* @timeComplexity O(n^2) - Quadratic time complexity due to nested loops, where n is the length of the input array.
43+
* @spaceComplexity O(1) - Constant space complexity as no additional data structures are used.
44+
*/
45+
const bruteForce = (nums: number[], target: number): number[] => {
46+
// Iterate over each element in the array.
47+
for (let i = 0; i < nums.length; i++) {
48+
// Iterate over each subsequent element to form pairs.
49+
for (let j = i + 1; j < nums.length; j++) {
50+
// Check if the sum of the current pair equals the target.
51+
if (nums[i] + nums[j] === target) {
52+
// If found, return an array containing the indices of the two numbers.
53+
return [i, j];
54+
}
55+
}
56+
}
57+
58+
// If no pair is found, return an empty array.
59+
return [];
60+
};
61+
62+
export const leetcodeProblem: LeetcodeProblem = {
63+
name: "1. Two Sum",
64+
code: "1",
65+
tags: ["Array"],
66+
solutions: [
67+
{ name: "HashMap", implementation: hashMap },
68+
{ name: "Bruteforce", implementation: bruteForce },
69+
],
70+
};

‎src/arrays/1-two-sum/tests/index.bench.ts‎

Lines changed: 13 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -1,19 +1,18 @@
11
import { bench, describe } from "vitest";
22

3-
import type { InputTestData } from "@typings/input-data";
4-
import { twoSum } from "..";
3+
import { leetcodeProblem } from "..";
4+
import { TEST_DATA } from "./test-data";
55

6-
const TEST_DATA: InputTestData<{ nums: number[]; target: number }, number[]> = {
7-
input: { nums: [2, 7, 11, 15], target: 9 },
8-
expected: [0, 1],
9-
};
6+
const { name, solutions } = leetcodeProblem;
107

11-
describe("Two Sum (benchmark)", () => {
12-
const {
13-
input: { nums, target },
14-
} = TEST_DATA;
15-
16-
bench(`should find the indices of two numbers that add up to ${target}`, () => {
17-
twoSum(nums, target);
18-
});
8+
describe(name, () => {
9+
for (const { name, implementation } of solutions) {
10+
bench(name, () => {
11+
for (const {
12+
input: { nums, target },
13+
} of TEST_DATA) {
14+
implementation(nums, target);
15+
}
16+
});
17+
}
1918
});

‎src/arrays/1-two-sum/tests/index.spec.ts‎

Lines changed: 16 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -1,19 +1,23 @@
11
import { describe, expect, it } from "vitest";
22

3-
import { twoSum } from "..";
3+
import { leetcodeProblem } from "..";
44
import { TEST_DATA } from "./test-data";
55

6-
describe("Two Sum", () => {
7-
for (const {
8-
input: { nums, target },
9-
expected,
10-
} of TEST_DATA) {
11-
it(`should find the indices of two numbers that add up to ${target}`, () => {
12-
// Validate inputs
13-
expect(nums).toBeDefined();
14-
expect(target).toBeDefined();
15-
// Validate output
16-
expect(twoSum(nums, target)).toEqual(expected);
6+
describe(leetcodeProblem.name, () => {
7+
for (const { name, implementation } of leetcodeProblem.solutions) {
8+
describe(name, () => {
9+
for (const {
10+
input: { nums, target },
11+
expected,
12+
} of TEST_DATA) {
13+
it("should find the indices of two numbers that add up to target", () => {
14+
// Validate inputs
15+
expect(nums).toBeDefined();
16+
expect(target).toBeDefined();
17+
// Validate output
18+
expect(implementation(nums, target)).toEqual(expected);
19+
});
20+
}
1721
});
1822
}
1923
});

‎src/arrays/1-two-sum/tests/test-data.ts‎

Lines changed: 10 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -1,13 +1,19 @@
1-
import type { InputTestData } from "@typings/input-data";
1+
import type { InputTestData } from "shared/typings/input-data";
22

33
export const TEST_DATA: InputTestData<{ nums: number[]; target: number }, number[]>[] = [
44
// Basic cases within constraints:
55
{ input: { nums: [2, 7, 11, 15], target: 9 }, expected: [0, 1] },
66
{ input: { nums: [3, 2, 4], target: 6 }, expected: [1, 2] },
77
{ input: { nums: [5, 5], target: 10 }, expected: [0, 1] },
8-
9-
// Test cases at array length limits:
10-
{ input: { nums: Array(10000).fill(1), target: 2 }, expected: [0, 1] },
8+
{ input: { nums: [3, 2, 4, 7, 9, 11, 15], target: 26 }, expected: [5, 6] },
9+
{ input: { nums: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], target: 19 }, expected: [8, 9] },
10+
{
11+
input: {
12+
nums: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20],
13+
target: 39,
14+
},
15+
expected: [18, 19],
16+
},
1117

1218
// Test cases at element value limits:
1319
{ input: { nums: [-1000000000, 0, 1000000000], target: 0 }, expected: [0, 2] },
@@ -16,8 +22,4 @@ export const TEST_DATA: InputTestData<{ nums: number[]; target: number }, number
1622
// Test cases with valid solutions but near value limits:
1723
{ input: { nums: [-999999999, 1], target: -999999998 }, expected: [0, 1] },
1824
{ input: { nums: [999999998, 1], target: 999999999 }, expected: [0, 1] },
19-
20-
// Test case with no solution
21-
{ input: { nums: [2], target: 4 }, expected: [] },
22-
{ input: { nums: [2, 3], target: -5 }, expected: [] },
2325
];

‎src/arrays/121-best-time-to-buy-and-sell-stock/tests/index.bench.ts‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
import { bench, describe } from "vitest";
22

3-
import type { InputTestData } from "@typings/input-data";
3+
import type { InputTestData } from "shared/typings/input-data";
44
import { maxProfit } from "..";
55

66
const TEST_DATA: InputTestData<number[], number> = { input: [7, 1, 5, 3, 6, 4], expected: 5 };

‎src/arrays/121-best-time-to-buy-and-sell-stock/tests/test-data.ts‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
import type { InputTestData } from "@typings/input-data";
1+
import type { InputTestData } from "shared/typings/input-data";
22

33
export const TEST_DATA: InputTestData<number[], number>[] = [
44
// Basic cases:

‎src/arrays/238-product-of-array-except-self/tests/index.bench.ts‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
import { bench, describe } from "vitest";
22

3-
import type { InputTestData } from "@typings/input-data";
3+
import type { InputTestData } from "shared/typings/input-data";
44
import { productExceptSelf } from "..";
55

66
const TEST_DATA: InputTestData<number[], number[]> = {

0 commit comments

Comments
 (0)