Relative Sort Array Javascript

Question

I am working on a problem on LeetCode and having some troubles

https://leetcode.com/problems/relative-sort-array/

Instructions: Given two arrays arr1 and arr2, the elements of arr2 are distinct, and all elements in arr2 are also in arr1.

Sort the elements of arr1 such that the relative ordering of items in arr1 are the same as in arr2. Elements that don't appear in arr2 should be placed at the end of arr1 in ascending order.

Example 1:

Input: arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6] Output: [2,2,2,1,4,3,3,9,6,7,19]

my attempt:

var relativeSortArray = function(arr1, arr2) {
    let arr =[]
    let end =[]
    for (i=0; i<arr2.length; i++){
        for (j=0; j<arr1.length; j++){
            if(arr2[i] == arr1[j]){
                arr.push(arr1[j])
            }else{
                end.push(arr1[j])
            }
        }
    }
    end.sort((a,b) => a-b)
    console.log(end)
    return arr
};

The If conditional works but the else condition isn't and I can't figure out why.

I think console.log(end) should give me the two numbers not in arr2 but it instead gives me:

[
  1, 1, 1,  1,  1,  2,  2,  2,  2, 2, 2, 2,
  2, 2, 2,  2,  2,  2,  2,  2,  3, 3, 3, 3,
  3, 3, 3,  3,  3,  3,  4,  4,  4, 4, 4, 6,
  6, 6, 6,  6,  7,  7,  7,  7,  7, 7, 9, 9,
  9, 9, 9, 19, 19, 19, 19, 19, 19
]

Why is this happening?

Thanks!!!

your logic is wrong, just iterate through arr1 check if the value is in arr2 by indexOf function — Dathan
– Dathan, Commented Jul 24, 2020 at 16:46
Your end array is that big because in every iteration of arr2 you're finding the same missing elements over and over again. — Carlos Roso
– Carlos Roso, Commented Jul 24, 2020 at 16:47
@AkashDathan the results are telling me it is wrong. I don't understand HOW it is wrong. I see it as if they are the same push here, if not push there. Why does that not work? — AylaWinters
– AylaWinters, Commented Jul 24, 2020 at 16:56
First i = 0. Then you go through all the items in arr1, find the missing ones, and add them to end. Then, i = 1, then you go through all the items in arr1, find the missing ones, and add them to end. Then, i = 2, then.... — Carlos Roso
– Carlos Roso, Commented Jul 24, 2020 at 16:59

Nina Scholz · Accepted Answer · 2020-07-24 17:10:40Z

4

You could take an object for the position of a value and take a large value like Number.MAX_VALUE as default value. If the delta is zero sort by value.

Taking a delta is a standard by using Array#sort. This returns a value smaller than zero, zero or greater than zero, depending on the values. The sort method receives this values and keeps or swaps the values.

const
    relativeSort = (array, given) => {
        const order = Object.fromEntries(given.map((v, i) => [v, i + 1]));
        return array.sort((a, b) =>
            (order[a] || Number.MAX_VALUE) - (order[b] || Number.MAX_VALUE) ||
            a - b
        );
    };

console.log(...relativeSort([2, 3, 1, 3, 2, 4, 6, 7, 9, 2, 19], [2, 1, 4, 3, 9, 6]));

edited Jul 24, 2020 at 17:10

answered Jul 24, 2020 at 16:48

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

AylaWinters Over a year ago

This code does work, could you help me to understand how?

Carlos Roso Over a year ago

@AndreTheTallGuy when you use the .sort function with a callback, you need a way to tell "a goes before b". You can't use the values here, your criteria is the position where those values should go. You get that criteria by building an object that maps values vs. positions from arr2, like order = {2: 1, 1: 2, 4: 3, 3: 4, 9: 5, 6: 6}. Then use those indexes to compare "ah, 3 goes before 9 because order[3] = 4 and order[9] = 5, that means 4-5 < 0, so 3 goes indeed before 9". For numbers without order you assume they go in the tail by assigning them an "infinite" position.

Shuki · Accepted Answer · 2020-07-24 16:58:18Z

0

In each iteration of arr2: all the numbers that are different from the current number are pushed to the end array

For example,

First iteration - compare number (2) and you will end up with:

arr: [2,2,2]

end: [3,1,3,4,6,7,9,19]

Second iteration - compare number (1) and you will end up with:

arr: [2,2,2,1]

end: [3,1,3,4,6,7,9,19] + [2,3,3,2,4,6,7,9,2,19]

try to debug your code to follow the flow

answered Jul 24, 2020 at 16:58

Shuki

413 bronze badges

2 Comments

AylaWinters Over a year ago

Why would end equal [3,1,3,4,6,7,9,19] ?

Shuki Over a year ago

In the first iteration, you are pushing all the items that are !=2 In the second iteration, you are pushing all the items that are !=1 ...

Kartik Verma · Accepted Answer · 2022-07-05 14:11:14Z

0

class Solution:
    def relativeSortArray(self, arr1: list[int], arr2: list[int]) -> list[int]:
        arr = []
        for i in arr2:
            value = arr1.count(i)
            for j in range(value):
                arr.append(i)
                arr1.remove(i)
        arr1.sort()
        return arr+arr1
obj = Solution()
arr1 = [28,6,22,8,44,17]
arr2 = [22,28,8,6]
result = obj.relativeSortArray(arr1,arr2)
print(result)

answered Jul 5, 2022 at 14:11

Kartik Verma

11 bronze badge

1 Comment

ahuemmer Over a year ago

Please don't post code-only answers but rather explain your approach a little in textual form: Why and how does it work? How does it differ from the other answers given?

Collectives™ on Stack Overflow

Relative Sort Array Javascript

3 Answers 3

2 Comments

2 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related