01-Big-O-FrequencyCounter/01-1-frequencyCounter-PATTERN-same.js at master · 4pmAlgorithm/01-Big-O-FrequencyCounter · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
//FREQUENCY COUNTER
//
//write a function called same, which accepts two arrays. The function should return true if every value in the array has it's corresponding value squared in the second array. The frequency of values must be the same.


//////////////////////////////////////////////
///////// **********  O(n²) naive, slower, more expensive ********** ///////
/////////////////////////////////////////////

// function same(arr1, arr2){
//     if(arr1.length !== arr2.length){
//         return false;
//     }
//     for(let i = 0; i < arr1.length; i++){ //arr1[1] === 2
//         let correctIndex = arr2.indexOf(arr1[i] ** 2) //2 //iterate all the element in the arr1 so it takes longer to look for the element. It is also nested so it becomes O(n ² sq 2)
//         //console.log(i)
//         //console.log(3 ** 2)
//         //console.log(correctIndex)
//         if(correctIndex === -1) { //if it doesn't exist
//           return false;
//         }
//         console.log(arr2);
//         arr2.splice(correctIndex, 1) //
//     }
//     return true;
// }
//same([1,2,3,2], [9,1,4,4])


// const same = (arr1, arr2) => {
//   if(arr1.length !== arr2.length){
//     return false
//   }
//   for (let i = 0 ; i < arr2.length; i++){
//     let currentIdx = arr2.indexOf(arr1[i] ** 2)
//     if (currentIdx === -1){
//       return false
//     }
//     arr2.splice(currentIdx, 1)
//   }
//   return true
// }


//////////////////////////////////////////////
///////// **********  O(n) ********** ///////
/////////////////////////////////////////////

//two separate loops are better than nested loops.

//const same = (arr1, arr2) => {
//   if(arr1.length !== arr2.length){
//     return false
//   }

//   let frequencyCounter1 = {}
//   let frequencyCounter2 = {}

//   for(let val of arr1){
//     //console.log("val", val)
//     // console.log("frequencyCounter1[val]", frequencyCounter1[val])
//     frequencyCounter1[val] = (frequencyCounter1[val] || 0 ) + 1
//     //console.log("frequencyCounter1[val] AFTER",frequencyCounter1[val])
//   }
//   console.log("::arr1::", frequencyCounter1)


//   for(let val of arr2){
//   frequencyCounter2[val] = (frequencyCounter2[val] || 0 ) + 1
//   }
//   console.log("::arr2::",frequencyCounter2)

//   for (let key in frequencyCounter1){
//     if(!(key ** 2 in frequencyCounter2)){
//       return false
//     }
//     if(frequencyCounter2[key ** 2] !== frequencyCounter1[key]){
//       return false
//     }
//   }
//   return true
// }
// same([1,2,3,2], [9,1,4,4])


//////////////////////////////////////////////
///////// **********  O(n) ********** ///////
/////////////////////////////////////////////
const same = (arr1, arr2) => {
  if(arr1.length !== arr2.length){
    return false
  }

  let freqCounter1 = {}
  let freqCounter2 = {}

  for (let val of arr1){
    freqCounter1[val] = (freqCounter1[val] || 0 ) + 1
  }

  for (let val of arr2){
    freqCounter2[val] = (freqCounter2[val] || 0 ) + 1
  }
  console.log("::1::", freqCounter1)
  console.log("::2::", freqCounter2)

  //freqCounter1 key ** 2 === freqCounter2 key
  //then vals are the same

  for (let key in freqCounter1){ //1,2,3
    //console.log(key)
    //console.log("***", (key in freqCounter2)) //true or false
    //1. check key
    if( !(key ** 2 in freqCounter2) ){
      return false
    }
    //2. check values are the same
    if( freqCounter2[key ** 2] !== freqCounter1[key]){
      return false
    }
  }
  return true
}

same([1,2,3,2], [9,1,4,4])