READ FIRST: As noted in the comments and on the twitter thread, the solution in part 1 is not necessarily a performant one. A second solution will ...
For further actions, you may consider blocking this person and/or reporting abuse
A better approach:
Runtime: O(n)
Iterate over A and store each values frequency as:
if i exists in D, then D[i]=D[i]+1
else, D[i]=1
Iterate over D and sum half of each key-value pair.
Hello Bhavesh, thank you for your input. This is the first solution and not necessarily the most performant one as I have stated in the video. If you look at the gist that was created for this project here Sock merchant solutions you will that the second solution that is coming in part 2 is using the dictionary approach tou have suggested
javascript
function stockAndCount( n, arr ) {
let pairs = 0;
const colors = arr.reduce((acc, val) => {
(!!acc[val]) ? acc[val] += 1 : acc[val] = 1;
return acc;
}, {});
}
Since this is unassuming of who is watching and what the level is, I start with the simple easy to grasp and evolve to the 'better' solution, better being relative here.
Stay tuned for the next episode and the reasoning why solution 2 will be a better approach.
Cheers
Good work, Sir.
Could we add 0.5 to avoid reiteration and round up when getting the value for a specific color?
Reiteration is prevented by skipping to 2 indexes down if a match is found. I’m not clear on how 0.5 will help here since we are looking at full pairs values
Yes, you're right. I somehow didn't notice you were using i++ and i+=1.
Sorry.
The 0.5 comment was regarding Bavesh's step 4, sorry I was not clear.
Thanks for this. I used a similar approach but forgot about the built-in sort method. Also, really appreciated your preface, which is very encouraging, esp. for someone who felt crushed for not being able to solve the "easy" challenge.
Hey Annie thank you for the kind words and I'm so happy that you found the article helpful. No worries about being crushed we all go through those phases no matter how far we evolve in our careers.
Keep at it, and don't be hard on yourself. Speeding and rushing are two different things so let us all keep pacing ourselves.
Take care 🙂
I had the same idea as Bhavesh but looking at the code in the article (I could not watch the video so sorry if it's in there), I'm a little confused.
Is arr populated with only the color integer? Like [1,2,1,1,3] for example?
Also, if you have something like [1,1,1], does the function need to return 1 or 2?
1 pair and 1 lonely sock?
Or 2 possible pairs?
Yes array is only populated with color integer and the challenge is specific about actual pairs so no possible. [1,1,1] should return 1 to satisfy the exercise requirements
Ady
Thanks for this...
Its helping me understand the order of computation better
So overall it is O(nlogn) * O(n)
// Complete the sockMerchant function below.
func sockMerchant(n: Int, ar: [Int]) -> Int {
var pair = 0
let sortedArr = ar.sorted() // O(nlogn)
var i=0
while (i<(sortedArr.count-1)) { // O(nlogn * n)
if sortedArr[i]==sortedArr[i+1]{
pair += 1
i += 1
}
i += 1
}
return pair
}
sockMerchant(n: 9, ar: [10, 20, 20, 10, 10, 30, 50, 10, 20])
my version:
let ar = [1, 2, 1, 2, 1, 3, 2,1]
function sockMatching(ar) {
let tmp = [];
let dict = {}
let totalPares = 0;
ar.forEach(p => {
let idPar = 'p' + p;
if (!tmp.includes(p)) {
tmp.push(p);
dict[idPar] = 1;
} else {
dict[idPar]++;
if (dict[idPar] === 2) {
totalPares++;
dict[idPar] = 0;
}
}
})
return totalPares;
}
console.log(sockMatching(ar));
What is the time complexity on this one?