educative.io

Benefit of Sorting

Courses
,
#1

Whilst i understand that sorting allows one to use the left and right pointers, given this an O(n^2) what’s the benefit of sorting rather than going through the input?

One could achieve the same time complexity with two loops O(n^2) without the sort step. Or have I missed something?

#2

Have you tried writing this solution? It will be a good exercise to try it and find out why it can’t be done in O(n^2) without sorting. Please do share your findings.

#3

Did have a play and see your point, my initial thinking was something like this (note C# and probably has syntax errors)
Dictionary<int, List<int[]>> twoSums = new Dictionary<int, List<int[]>>()

// O(n^2) time
// O(n) space
for (int i = 0; i < arr.Length - 1; i++) {
    for (int j = i + 1; < arr.Length; j++) {
        var sum = arr[i] + arr[j];
        if (twoSums.ContainsKey[sum]) {
            twoSums[sum].Add(new int[2] { i, j});
        } else {
            var list new List<int[]> {new int[2] { i, j}};
            twoSums.Add(sum, list);
        }
    } 
}

int closestNumber = Int32.MaxValue;
int[] indexes = new int[3];

for (int i = 0; i < arr.Length; i++) {
    // Do something here 
    // Yet requires sorting the keys unless using a sorted dictionary
}

Only way to avoid the sorting would be to possibly use a sorted collection