Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Refactor JS - Array & Hash#445

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.

Already on GitHub?Sign in to your account

Merged
mitchellirvin merged 1 commit intoneetcode-gh:mainfromaakhtar3:array-hash
Sep 19, 2022
Merged
Show file tree
Hide file tree
Changes fromall commits
Commits
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
80 changes: 72 additions & 8 deletionsjavascript/1-Two-Sum.js
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -1,15 +1,79 @@
/**
* Brute Force - Linear Search
* Time O(N^2) | Space O(1)
* https://leetcode.com/problems/two-sum/
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function (nums, target) {
let map = {};
for (let i = 0; i < nums.length; i++) {
if (target - nums[i] in map) {
return [map[target - nums[i]], i];
} else {
map[nums[i]] = i;
var twoSum = (nums, target) => {
for (let curr = 0; curr < nums.length; curr++) {/* Time O(N) */
const complement = target - nums[curr];

for (let next = (curr + 1); next < nums.length; next++) {/* Time O(N) */
const num = nums[next];

const isTarget = num === complement
if (isTarget) return [ curr, next ];
}
}
};

return [ -1, -1 ];
}

/**
* Hash Map - 2 Pass
* Time O(N) | Space O(N)
* https://leetcode.com/problems/two-sum/
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = (nums, target) => {
const map = getMap(nums); /* Time O(N) | Space O(N) */

return getSum(nums, target, map)/* Time O(N) */
}

const getMap = (nums, map = new Map()) => {
for (let index = 0; index < nums.length; index++) {/* Time O(N) */
map.set(nums[index], index); /* Space O(N) */
}

return map
}

const getSum = (nums, target, map) => {
for (let index = 0; index < nums.length; index++) {/* Time O(N) */
const complement = target - nums[index];
const sumIndex = map.get(complement);

const isTarget = map.has(complement) && (map.get(complement) !== index)
if (isTarget) return [ index, sumIndex ]
}

return [ -1, -1 ];
}

/**
* Hash Map - 1 Pass
* Time O(N) | Space O(N)
* https://leetcode.com/problems/two-sum/
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = (nums, target, map = new Map()) => {
for (let index = 0; index < nums.length; index++) {/* Time O(N) */
const num = nums[index];
const complement = (target - num);
const sumIndex = map.get(complement);

const isTarget = map.has(complement)
if (isTarget) return [ index, sumIndex ];

map.set(num, index); /* Space O(N) */
}

return [ -1, -1 ];
}
140 changes: 70 additions & 70 deletionsjavascript/128-Longest-consecutive-sequence.js
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -1,94 +1,94 @@
//////////////////////////////////////////////////////////////////////////////
// Linear Search With A Hash Map
// Time: O(n)
// Space: O(n)
// This solution only makes one pass over the `nums` array and is the highest
// performing solution.
//////////////////////////////////////////////////////////////////////////////

/**
* Brute Force
* Greedy - Max Score
* Time O (N^3) | Space O(1)
* https://leetcode.com/problems/longest-consecutive-sequence/
* @param {number[]} nums
* @return {number}
*/
function longestConsecutive(nums) {
if (!nums.length) {
return 0;
}
var longestConsecutive = (nums, maxScore = 0) => {
for (const num of nums) {/* Time O(N) */
let [ currNum, score ] = [ num, 1 ];

const map = Object.create(null);
let max = 0;

for (const num of nums) {
if (num in map) {
continue;
while (isStreak(nums, (currNum + 1))) {/* Time O(N * N) */
currNum++;
score++;
}

const prev = num - 1;
const next = num + 1;
let len = 1;

if (prev in map) {
if (next in map) {
len += map[prev] + map[next];
map[prev - map[prev] + 1] = len;
map[next + map[next] - 1] = len;
} else {
len += map[prev];
++map[prev - map[prev] + 1];
}
} else if (next in map) {
len += map[next];
++map[next + map[next] - 1];
}
map[num] = len;
max = Math.max(max, len);
maxScore = Math.max(maxScore, score);
}

returnmax;
returnmaxScore;
}

//////////////////////////////////////////////////////////////////////////////
// Linear Search With A Hash Set
// Time: O(n)
// Space: O(n)
// This solution does three passes over the `nums` array. A first pass to
// setup the hash set. A second pass to find the numbers that mark the
// beginning of a sequence. A third pass to calculate the length of each
// sequence. The nested `while` loop does not cause quadratic calculations as
// it is only initiated on the first number of each sequence.
//////////////////////////////////////////////////////////////////////////////
const isStreak = (nums, num) => {
for (let i = 0; i < nums.length; i++) {/* Time O(N) */
const isEqual = nums[i] === num
if (isEqual) return true;
}

return false;
}

/**
* Sort - HeapSort Space O(1) | QuickSort Space O(log(K))
* Greedy - Max Score
* Time O (N * log(N)) | Space O(1)
* https://leetcode.com/problems/longest-consecutive-sequence/
* @param {number[]} nums
* @return {number}
*/
function longestConsecutive(nums) {
let len = nums.length;
if (!len) {
return 0;
var longestConsecutive = (nums) => {
if (!nums.length) return 0;

nums.sort((a, b) => a - b);/* Time O(N * log(N)) | Space O(1 || log(N)) */

return search(nums); /* Time O(N) */
}

const search = (nums) => {
let [ maxScore, score ] = [ 1, 1 ];

for (let i = 1; i < nums.length; i++) {/* Time O(N) */
const isPrevDuplicate = nums[i - 1] === nums[i]
if (isPrevDuplicate) continue

const isStreak = nums[i] === ((nums[i - 1]) + 1)
if (isStreak) { score++; continue; }

maxScore = Math.max(maxScore, score);
score = 1;
}
const set = new Set(nums);
let max = 0;

for (let i = 0; i < nums.length; i++) {
const num = nums[i];
return Math.max(maxScore, score);
}

if (set.has(num - 1)) {
continue;
}
/**
* Hash Set - Intelligent Sequence
* Greedy - Max Score
* Time O (N) | Space O(N)
* https://leetcode.com/problems/longest-consecutive-sequence/
* @param {number[]} nums
* @return {number}
*/
var longestConsecutive = (nums, maxScore = 0) => {
const numSet = new Set(nums); /* Time O(N) | Space O(N) */

let currentMax = 1;
while (set.has(num + currentMax)) {
currentMax++;
}
for (const num of [ ...numSet ]) { /* Time O(N) */
const prevNum = num - 1;

if (currentMax > max) {
max = currentMax;
}
if (max > len / 2) {
break;
if (numSet.has(prevNum)) continue;/* Time O(N) */

let [ currNum, score ] = [ num, 1 ];

const isStreak = () => numSet.has(currNum + 1)
while (isStreak()) { /* Time O(N) */
currNum++;
score++;
}

maxScore = Math.max(maxScore, score);
}

returnmax;
}
returnmaxScore;
}
81 changes: 61 additions & 20 deletionsjavascript/217-Contains-Duplicate.js
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -1,31 +1,72 @@
/**
* Brute Force - Linear Search
* Time O(N^2) | Space O(1)
* https://leetcode.com/problems/contains-duplicate/
* @param {number[]} nums
* @return {boolean}
*/

//First method using Set() (exit early if true)
var containsDuplicate = function (nums) {
const numsSet = new Set();
for (const i of nums) {
if (numsSet.has(i)) {
return true;
var containsDuplicate = (nums) => {
for (let right = 0; right < nums.length; right++) {/* Time O(N) */
for (let left = 0; left < right; left++) { /* Time O(N) */
const isDuplicate = nums[left] === nums[right];
if (isDuplicate) return true;
}
numsSet.add(i);
}

return false;
};
}

/**
* Sort - HeapSort Space O(1) | QuickSort Space O(log(N))
* Time O(N * log(N)) | Space O(1)
* https://leetcode.com/problems/contains-duplicate/
* @param {number[]} nums
* @return {boolean}
*/
var containsDuplicate = (nums) => {
nums.sort((a, b) => a - b);/* Time O(N * log(N)) | Space O(1 || log(N)) */

//Second method using Map() (Has to map entire array but code is more readable)
var containsDuplicate = function (nums) {
//create a new hashmap with all the items in the array. Any duplicates will be removed.
const totalWithoutDuplicates = new Map(nums.map((i) => [i]));
return hasDuplicate(nums);
}

//check if the size of the initial array is larger than the new hashmap.
return totalWithoutDuplicates.size !== nums.length;
};
const hasDuplicate = (nums) => {
for (let curr = 0; curr < (nums.length - 1); curr++) {/* Time O(N) */
const next = (curr + 1);

const isNextDuplicate = nums[curr] === nums[next];
if (isNextDuplicate) return true;
}

//Third method using Set() (Fastest runtime at 91.95% and very readable code)
var containsDuplicate = function (nums) {
//Pass the array into a Set() (which removes duplicates) and then compare its size to the original array.
return new Set(nums).size !== nums.length;
return false;
}

/**
* Hash Set
* Time O(N) | Space O(N)
* https://leetcode.com/problems/contains-duplicate/
* @param {number[]} nums
* @return {boolean}
*/
var containsDuplicate = (nums) => {
const numsSet = new Set(nums);/* Time O(N) | Space O(N) */
const isEqual = numsSet.size === nums.length;

return !isEqual;
};

/**
* Hash Set - Early Exit
* Time O(N) | Space O(N)
* https://leetcode.com/problems/contains-duplicate/
* @param {number[]} nums
* @return {boolean}
*/
var containsDuplicate = (nums, numsSet = new Set()) => {
for (const num of nums) {/* Time O(N) */
if (numsSet.has(num)) return true;

numsSet.add(num); /* Space O(N) */
}

return false;
};
Loading
[8]ページ先頭
©2009-2025 Movatter.jp