- 문제 해결 전략을 만들자
- 기본적인 문제 해결 패턴을 마스터하자
Q : Write a function called same, which accepts two arrays. The function should return true if every value in the array has it's coreesponding value squared in the second array. The frequency of values must be the same.
same([1,2,3], [4,1,9]) // ture
same([1,2,3], [1,9]) // flase
smae([1,2,1], [4,4,1]) // flase (must be same frequency)A
- Time Complexity - O(N^2)
function same(arr1, arr2) {
if (arr1.length !== arr2.length) {
return false;
}
for (let i = 0; i < arr1.length; i++) {
let correctIndex = arr2.indexOf(arr1[i] ** 2);
if (correctIndex === -1) {
return false;
}
// arr2에 존재하는 arr1의 요소를 삭제
console.log(arr2);
arr2.splice(correctIndex, 1);
}
return true;
}- Time Complexity - O(n)
function same(arr1, arr2){
if(arr1.length !== arr2.length){
return false;
}
let frequencyCounter1 = {}
let frequencyCounter2 = {}
for(let val of arr1){
frequencyCounter1[val] = (frequencyCounter1[val] || 0) + 1
}
for(let val of arr2){
frequencyCounter2[val] = (frequencyCounter2[val] || 0) + 1
}
console.log(frequencyCounter1);
console.log(frequencyCounter2);
for(let key in frequencyCounter1){
if(!(key ** 2 in frequencyCounter2)){
return false
}
if(frequencyCounter2[key ** 2] !== frequencyCounter1[key]){
return false
}
}
return true
}Q : Given to strings, write a function to determine if the second string is an anagram of the first.
An anagram is a word, phrase, or name formed by rearrangin the letters of another, such as cinema, formed from iceman. - 글자 조합해서 새로운 단어 만드는것!
validAnagram('', '') //true
validAnagram('aaz', 'zza') // false
validAnagram('anagram', 'nagaram') //trueA
const validAnagram(first, second) {
// 1. 글자수 비교
if (first.length !== second.length) {
return false;
}
const lookup = {};
for (let i = 0; i < first.length; i++) {
let letter = first[i];
// 글자가 있으면 +1 없으면 1
lookup[letter] ? lookup[letter] += 1 : lookup[letter] = 1;
}
for ( let i = 0; i < second.length; i++) {
let letter = second[i]
// 2. 두 문자열 비교하기
// 두번째 문자를 첫번째 문자열이 안가지고 있다면
if (!lookup[letter]) {
return false;
} else {
// 아니면 첫번째 문자열 갯수 하나 감소
lookup[letter] -= 1;
}
}
return true;
}Creating pointers or values that correspond to an index or position and move towards the beginning, end or middle based on a certain condition
Very efficient for solving problems with minimal space complexity as well
Q1 : Write a function called sumZero which accepts a **sorted **array of integers. The function should find the first pair where the sum is 0.
Return an array that includes both values that sum to zero or undefined if a pair does not exist.
sumZero([-3, -2, -1, 0, 1, 2, 3]) // [-3, 3]
sumZero([-2, 0, 1, 3]) // undefined
sumZero([1, 2, 3]) // undefinedA
- Time Complexity : O(N^2)
- Space Complexity - O(1)
const sumZero = arr => {
for(let i = 0; i < arr.length; i++) {
for(let j = i + 1; j < arr.length; j++) {
if(arr[i] + arr[j] === 0) {
return [arr[i], arr[j]];
}
}
}
}- TIme Complexity : O(N)
- Space Complexity : O(1)
const sumZero = arr => {
let left = 0;
let right = arr.length - 1;
while (left < right) {
let sum = arr[left] + arr[right];
if(sum === 0) {
return [arr[left], arr[right]];
} else if (sum > 0) {
right--;
} else {
left++;
}
}
}Q : Implement a function called countUniquevalues,
which accepts a sorted array, and counts the
unique values in the array. There can be negative
numbers in the array, but it will always be sorted.
countUniquevalues([1, 1, 1, 1, 1, 2]) //2
countUniquevalues([1, 2, 3, 4, 4, 4, 7, 7, 12, 12, 13]) // 7
countUniquevalues([]) // 0
countUniquevalues([-2, -1, -1, -0, 1]) // 4A :
const countUniqueValues = arr => {
if (arr.length === 0) {
return 0;
}
let i = 0;
for (let j = 0; j < arr.length; j++) {
if (arr[i] !== arr[j]) {
i++;
arr[i] = arr[j];
}
}
return i + 1;
};This pattern involves creating a window which can either
be an array or number from one position to anotherDepending on a certain condition, the window either increases
or closes (and a new window is created)Very useful for keeping track of a subset of data in an
array / string etc.
Q : Wrtie a function called maxSubarraySum which accepts
an array of integers and a number called n. The function should
calculate the maximum sum of n consecutive elements in the array.
maxSubarraySum([1, 2, 5, 2, 8, 1, 5], 2) // 10
maxSubarraySum([1, 2, 5, 2, 8, 1, 5], 4) // 17
maxSubarraySum([4, 2, 1, 6], 1) // 6
maxSubarraySum([], 4) // nullA :
- Time Complexity : O(N^2)
function maxSubarraySum(arr, num) {
if ( num > arr.length) {
return null;
}
var max = -Infinity;
for (let i = 0; i < arr.length - num + 1 ; i++) {
temp = 0;
for(let j = 0; j < num; j++) {
temp += arr[i + j];
}
if (temp > max) {
max = temp;
}
}
return max;
}- Time Complexity : O(N)
function maxSubarraySum(arr, num) {
let maxSum = 0;
let tempSum = 0;
if (arr.length < num) return null;
for (let i = 0; i < num; i++) {
maxSum += arr[i];
}
tempSum = maxSum;
for (let i = num; i < arr.length; i++) {
tempSum = tempSum - arr[i - num] + arr[i];
maxSum = Math.max(maxSum, tempSum);
}
return maxSum;
}- idea : 처음부터 배열을 다시 더하는 것이 아니라 처음 숫자를 빼고 다음 숫자를 더한다.
This pattern involves dividing a data set into smaller chunks and then repeating a
process with a subset of data.This pattern can tremendously decrease time complexity
Q : Given a sorted array of integers, write a function
called search, the accepts a value and returns the
index where the value passed to the function is located.
if the value not found, return -1
search([1, 2, 3, 4, 5, 6], 4) // 3
search([1, 2, 3, 4, 5, 6], 6) // 6
search([1, 2, 3, 4, 5, 6], 11 ) // -1 A :
- Time Complexity : O(N)
function search(arr, val) {
for(let i = b; i < arr.length; i++) {
if(arr[i] === val) {
return i;
}
}
return -1;
}- Time complexity : Log(N)
function search(array, val) {
let min = 0;
let max = array.length -1;
while (min <= max) {
let middle = Math.floor((min + max) / 2);
let currentElement = array[middle];
if (array[middle] < val) {
min = middle + 1;
} else if (array[middle] > val) {
max = middle - 1;
} else {
return middle;
}
}
return -1;
}