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. Implementation
  4. Almost Sorted
  5. Discussions

Almost Sorted

Sort by

recency

|

505 Discussions

|

  • wifivop476
     + 0 comments

    you are probably missing this case where swap can occur at two different index check swap at 2 condition adjacent values and values that are far apart. cam free

  • vutrantrung14821
     + 0 comments
    def almostSorted(A):
    p=[]
    q=[]
    for i in range (len(A)-1):
       if A[i]>A[i+1]:
           q.append(i)
           p.append(i+1)
    if len(p)==2:
       A[q[0]],A[p[1]]=A[p[1]],A[q[0]]
       if A==sorted(A):
         print(f"yes\nswap {q[0]+1} {p[1]+1}")
       else:
         print('no')
    elif len(p)==1:
       A[q[0]],A[p[0]]=A[p[0]],A[q[0]]
       if A==sorted(A):
         print(f"yes\nswap {q[0]+1} {p[0]+1}")
       else:
        print('no')
    elif len(p)>2:
       pq=sorted(set(p)|set(q))
       A[pq[0]:pq[len(pq)-1]+1]=A[pq[0]:pq[len(pq)-1]+1][::-1]
       if A==sorted(A):
         print('yes')
         print(f"reverse {pq[0]+1} {pq[-1]+1}")
       else:
        print('no')

  • tangjiaqing
     + 0 comments
    1. Scan sequence of number from the beginning.
    2. Identify whether the scanned sequence is swappable or reversable or not.
    3. After scanning, find out whether the sequence can be arranged by swap or reverse.
    4. It doesn't need to actually swap or reverse any elements. Maintaining the points is enough.

    https://github.com/jiaqing123/HackerRankApp/blob/master/HackerRankApp/Problems/AlmostSorted.cs

  • aryankatiyarak2
     + 0 comments

    // The "Almost Sorted" problem is another common problem in programming, often posed in coding competitions. It typically involves checking if you can sort an array by performing a limited number of operations. Here’s a detailed breakdown of the problem:

    // ### Problem Description // 1. Input: You are given an array of integers which is nearly sorted, meaning that most of the elements are in the correct order, except for a few out of place. // 2. Operations Allowed: You can perform the following operations: // - Reverse a subarray of the array, meaning you can select two indices and reverse the elements between them. // 3. Objective: Determine if the array can be sorted by reversing at most one subarray.

    // ### Steps to Solve // 1. Identify Out-of-Order Sections: // - Scan through the array to find the sections where the order is disrupted (where arr[i] > arr[i + 1]). // - Track the start and end points of these disrupted sections.

    // 2. Check Conditions: // - If there are no disruptions, the array is already sorted. // - If there are multiple out-of-order sections, the array cannot be sorted with just one operation. // - If there is exactly one out-of-order section (say from index l to r), reverse that section and check if the entire array becomes sorted.

    // 3. Boundary Conditions: // - When reversing the identified segment, check the potential impact on the elements immediately before and after that segment to ensure continuity.

    // ### Example // Consider the array: [1, 3, 5, 4, 2, 6]

    // 1. Disruptions are found between indices 2 (5) and 4 (2). // 2. The segment to reverse is [5, 4, 2] (from index 2 to 4). // 3. If you reverse this, you get [1, 3, 2, 4, 5, 6]. // 4. Now check the surrounding elements: // - 3 (index 1) and 2 (index 2) can cause a disruption, so the array is not sorted. // 5. However, if you find just one segment that, when reversed, leads to a sorted array, then it is confirmed that you can sort it with one operation.

    // ### Complexity // - The algorithm primarily involves scanning the array, which can be done in O(n) time, where n is the number of elements in the array.

    // ### Summary // The "Almost Sorted" problem challenges you to determine if a nearly sorted array can be put in order with minimal intervention (like reversing just one segment).

    // If you want deeper insights into the implementation or additional examples, let me know!

  • vuhuutuan0
     + 0 comments

    My answer in Typescript, note idea and improvement in comment

    const YES = 'yes', NO = 'no'
function almostSorted(arr: number[]): void {
    const check_is_sorted = (arr: number[]): boolean => {
        /**
         * idea: check over array, if is there any decrement, the array is not sorted
         * -> improve: can add [start] and [end] index to check in that range, small effectines
         */
        let start = 0
        let end = arr.length - 1;
        for (let i = start; i < end; i++) {
            if (arr[i] > arr[i + 1]) return false;
        }
        return true;
    }
    const check_can_swap = (arr: number[]): [number, number] | undefined => {
        /**
         * idea1: loop array with 2 param x, y. try swap and check_is_sorted on each
         * -> worked
         * -> improve: too many loop -> too many check -> too slow on large input -> check idea2
         * 
         * idea2: loop array once to find the point that decrement, then find the lowest
         * number in the rest of array, swap them once and check_is_sorted once
         * -> worked, just 1 loop and 1 check -> so fast
         */
        for (let i = 0; i < arr.length - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                let x = i
                let y = arr.indexOf(Math.min(...arr.slice(x + 1)))
                let arr_swaped = [...arr];[arr_swaped[x], arr_swaped[y]] = [arr_swaped[y], arr_swaped[x]];
                if (check_is_sorted(arr_swaped)) return [x + 1, y + 1]
                return
            }
        }
        return
    }
    const check_can_reserve = (arr: number[]): [number, number] | undefined => {
        /**
         * idea: check over array, find firsts decrement and then find firsts increment, that is 2 index
         * of sub-array that need to be reserve. reserve it and check_is_sorted
         * -> worked
         * -> improve: im not sure, it work well and fast, maybe don't create new array to save memory?
         */
        let x, y, i = 0
        while (true) {
            if (x != undefined && y != undefined) {
                let arr_reserve = [...arr.slice(0, x), ...arr.slice(x, y + 1).reverse(), ...arr.slice(y + 1)]
                if (check_is_sorted(arr_reserve)) return [x + 1, y + 1]
                break;
            }
            if (i >= arr.length - 1) break;
            if (x == undefined) {
                if (arr[i + 1] < arr[i]) x = i;
            } else {
                if (arr[i + 1] > arr[i]) y = i;
            }
            i++
        }
        return
    }

    // array has already sorted -> YES
    const is_sorted = check_is_sorted(arr)
    if (is_sorted) { console.log(YES); return; }

    // try swap
    const can_swap = check_can_swap(arr)
    if (!!can_swap) { let [x, y] = can_swap; console.log(YES); console.log(`swap ${x} ${y}`); return; }

    // try reverse
    const can_reserve = check_can_reserve(arr)
    if (!!can_reserve) { let [x, y] = can_reserve; console.log(YES); console.log(`reverse ${x} ${y}`); return; }

    // array can't be sorted by any way -> NO
    console.log(NO)
}