We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Sorting
  4. Lily's Homework
  5. Discussions

Lily's Homework

Sort by

recency

|

270 Discussions

|

  • kbssj1
     + 0 comments

    javascript

    function lilysHomework(arr) {

    let sorted = arr.slice().sort((a, b) => a - b);
    let arr2 = arr.slice();
    let check = {};
    let check2 = {};
    let ans = 0;
    let ans2 = 0;
    for (let i=0;i<sorted.length;++i) {
        check[sorted[i]] = i;
    }
    for (let i=0;i<sorted.length;++i) {
        check2[sorted[i]] = sorted.length-1-i;
    }

    for(let i=0;i<arr.length;) {
        if (check[arr[i]] != i) {
            let t = arr[i];
            let t_i = check[arr[i]];
            arr[i] = arr[check[arr[i]]];
            arr[t_i] = t;
            ++ans;
        } else {
            ++i;
        }    
    }
    
    for(let i=arr2.length - 1;i>0;) {
        if (check2[arr2[i]] != i) {
            let t = arr2[i];
            let t_i = check2[arr2[i]];
            arr2[i] = arr2[check2[arr2[i]]];
            arr2[t_i] = t;
            ++ans2;
        } else {
            --i;
        }    
    }
    
    return ans < ans2 ? ans : ans2;
}

  • kalbertalbert121
     + 0 comments

    Sort the Array Track Cycles Count Swaps = (cycle length - 1) I run the test array [3,4,2,5,1] ->output 4, but the expected answer is 2,why?

    def lilysHomework(arr): # Write your code here # Create a list of tuples where each tuple is (element, original_index) n = len(arr) arr_with_indices = [(arr[i], i) for i in range(n)]

    # Sort the array by the element values
arr_with_indices.sort(key=lambda x: x[0])

# To track visited elements
visited = [False] * n
swaps = 0

for i in range(n):
    # If the element is already visited or already in the correct position, skip it
    if visited[i] or arr_with_indices[i][1] == i:
        continue

    # Start a new cycle
    cycle_size = 0
    j = i
    while not visited[j]:
        visited[j] = True
        j = arr_with_indices[j][1]  # Move to the next element in the cycle
        cycle_size += 1

    # If there is a cycle of size `k`, it takes `k - 1` swaps to sort the cycle
    if cycle_size > 1:
        swaps += cycle_size - 1

return swaps

  • djiloumnov
     + 0 comments

    Solution in JS: function getNumberSwaps(arr, arrMap, sortedArr) { let numberOfSwaps = 0; for (let i = 0; i < sortedArr.length; i++) { if (sortedArr[i] !== arr[i]) { const tmp = arr[i]; const idxSource = arrMap[sortedArr[i]];

            arr[i] = arr[idxSource];
        arr[idxSource] = tmp;

        arrMap[tmp] = idxSource;
        arrMap[sortedArr[i]] = i;

        numberOfSwaps++;
    }
}

return numberOfSwaps;

    }

    function lilysHomework(arr) { const ascArr = arr.toSorted((a, b) => a - b); const descArr = arr.toSorted((a, b) => b - a);

    const arrMap = {};
arr.forEach((num, idx) => {
    arrMap[num] = idx
});
return Math.min(getNumberSwaps([...arr], { ...arrMap }, ascArr), getNumberSwaps(arr, arrMap, descArr));

    }

    `

  • wifivop476
     + 0 comments

    It's possible that a swap could move 2 numbers from where they start, to where they need to be, in a single swap with capzcut. Does this method take that into account? Simply comparing a sorted array to the original array, does not tell how many swaps it would take to get to the sorted array.

  • zettix1
     + 0 comments

    Pedantic.

    class Result {

    /*
     * Complete the 'lilysHomework' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts INTEGER_ARRAY arr as parameter.
     */

    public static int countSwaps(List<List<Integer>> indexToValueList) {
        int totalSwaps = 0;        
        Map<Integer, Integer>  indexToIndex = new HashMap<>();
        Set<Integer> startPositions = new HashSet<>();
        for (int i = 0; i <  indexToValueList.size(); i++) {
            indexToIndex.put(i,indexToValueList.get(i).get(0) );
        }
        startPositions.addAll(indexToIndex.values());
        int idx = 0;
        while (! startPositions.isEmpty()) {
            int currentSwaps = 0;
            int startPos = idx;
            int nextPos = indexToIndex.get(idx);
            startPositions.remove(startPos);
            int curpos = startPos;
            while (nextPos != startPos) {
                currentSwaps++;
                startPositions.remove(nextPos);
                nextPos = indexToIndex.get(nextPos);
                curpos = nextPos;

            }
            while (! startPositions.contains(idx)) {
                idx++;
                if (idx >= indexToIndex.size()) {
                    break;
                }
            }
            totalSwaps += currentSwaps;
        }
        return totalSwaps;
    }
    
    public static int lilysHomework(List<Integer> arr) {
         
        class SortByValueUp implements Comparator<List<Integer>>  {
        
        @Override
        public int compare(List<Integer> a, List<Integer> b) {
            int va = a.get(1);
            int vb = b.get(1);
            if (va > vb) {
                return 1;
            }
            if (va < vb) {
                return -1;
            }
            return 0;
          }
      }
      
      class SortByValueDown implements Comparator<List<Integer>> {
          
        @Override
        public int compare(List<Integer> a, List<Integer> b) {
            int va = a.get(1);
            int vb = b.get(1);
            if (va < vb) {
                return 1;
            }
            if (va > vb) {
                return -1;
            }
            return 0;  
          }
      }
      
    // Write your code here
        // minimum is sorted.  How many swaps to sort?
        // A sort is a permutation.  After sorting, count number
        // of things not in place.  All others must swap, and
        // swaps can be a cycle, e.g.:  a<->b, b<->c, c<->d, d<->a
        // or a mirror: a<->b.  4 swaps fix 4 in a ring, mirror fixes 2.
        // Hence we count the loops lengths, e.g. swaps.
        List<List<Integer> > indexToValueList1 = new ArrayList<>();
        List<List<Integer> > indexToValueList2 = new ArrayList<>();
        for (int i = 0; i < arr.size(); i++) {
            List<Integer> entry = new ArrayList<>();
            entry.add(i);
            entry.add(arr.get(i));
            indexToValueList1.add(entry);
            indexToValueList2.add(entry);
        }
        Collections.sort(indexToValueList1, new SortByValueUp());
        Collections.sort(indexToValueList2, new SortByValueDown());
        int s1 = countSwaps(indexToValueList1);
        int s2 = countSwaps(indexToValueList2);
        if (s1 < s2) {
            return s1;
        }
        return s2;
    }
}