LeetCode - Algorithms - 977. Squares of a Sorted Array

Problem

977. Squares of a Sorted Array

Java

1

class Solution {
    public int[] sortedSquares(int[] A) {
        int tmp = 0;
        for(int i=0;i<A.length;i++) {
            tmp = A[i];
            A[i]=tmp*tmp;
        }
        Arrays.sort(A);
        return A;        
    }
}

Submission Detail

• 132 / 132 test cases passed.
• Runtime: 2 ms, faster than 72.59% of Java online submissions for Squares of a Sorted Array.
• Memory Usage: 41.6 MB, less than 24.34% of Java online submissions for Squares of a Sorted Array.

Two Pointer

class Solution {
    public int[] sortedSquares(int[] A) {
        final int N = A.length;
        if (A[0] >= 0) {
            int tmp = 0;
            for (int i = 0; i < N; i++) {
                tmp = A[i];
                A[i] = tmp * tmp;
            }
            return A;
        } else {
            int[] r = new int[N];
            int left = 0, right = 0;
            int k = N - 1;
            for (int i = 0, j = N - 1; i <= j; ) {
                left = A[i] * A[i];
                right = A[j] * A[j];
                if (left < right) {
                    j--;
                    r[k--] = right;
                } else {
                    i++;
                    r[k--] = left;
                }
            }
            return r;
        }        
    }
}

Submission Detail

• 132 / 132 test cases passed.
• Runtime: 1 ms, faster than 100.00% of Java online submissions for Squares of a Sorted Array.
• Memory Usage: 41.2 MB, less than 73.53% of Java online submissions for Squares of a Sorted Array.

3

class Solution {
    public int[] sortedSquares(int[] A) {
        final int N = A.length;
        if (A[0] >= 0) {
            int tmp = 0;
            for (int i = 0; i < N; i++) {
                tmp = A[i];
                A[i] = tmp * tmp;
            }
            return A;
        } else if (A[N - 1] <= 0) {
            int[] r = new int[N];
            for (int i = 0; i < N; i++) {
                r[i] = A[N - 1 - i] * A[N - 1 - i];
            }
            return r;
        } else {
            int[] r = new int[N];
            int left = 0, right = 0;
            int k = N - 1;
            for (int i = 0, j = N - 1; i <= j; ) {
                left = A[i] * A[i];
                right = A[j] * A[j];
                if (left < right) {
                    j--;
                    r[k--] = right;
                } else {
                    i++;
                    r[k--] = left;
                }
            }
            return r;
        }       
    }
}

Submission Detail

• 132 / 132 test cases passed.
• Runtime: 1 ms, faster than 100.00% of Java online submissions for Squares of a Sorted Array.
• Memory Usage: 41.3 MB, less than 62.05% of Java online submissions for Squares of a Sorted Array.

4

class Solution {
    public int[] sortedSquares(int[] A) {
        final int N = A.length;
        int[] r = new int[N];
        int left = 0, right = 0;
        int k = N - 1;
        for (int i = 0, j = N - 1; i <= j; ) {
            left = A[i] * A[i];
            right = A[j] * A[j];
            if (left < right) {
                j--;
                r[k--] = right;
            } else {
                i++;
                r[k--] = left;
            }
        }
        return r;     
    }
}

Submission Detail

• 132 / 132 test cases passed.
• Runtime: 1 ms, faster than 100.00% of Java online submissions for Squares of a Sorted Array.
• Memory Usage: 41 MB, less than 85.39% of Java online submissions for Squares of a Sorted Array.