Java Solutions
Solution 1:\n\nTime complexity: O(n)\nSpace complexity: O(1)\n\n\nclass Solution \n{\n    public int[] sortArrayByParityII(int[] A) \n    {\n        int i = 0;\
**Solution 1:**\n\nTime complexity: `O(n)`\nSpace complexity: `O(1)`\n\n```\nclass Solution \n{\n    public int[] sortArrayByParityII(int[] A) \n    {\n        int i = 0;\n        int j = 1;\n        \n        while(i < A.length && j < A.length)\n        {\n            while(i < A.length && A[i] % 2 == 0) i += 2;\n            while(j < A.length && A[j] % 2 == 1) j += 2;\n            \n            if(i < A.length && j < A.length)\n                swap(A, i, j);\n        }\n        return A;\n    }\n    \n    private void swap(int[] A, int i, int j)\n    {\n        int temp = A[i];\n        A[i] = A[j];\n        A[j] = temp;\n    }\n}\n```\n\n**Solution 2:**\n\nTime complexity: `O(n)`\nSpace complexity: `O(1)`\n\n```\nclass Solution \n{\n    public int[] sortArrayByParityII(int[] A) \n    {\n        int evenIndex = 0;\n        int oddIndex = A.length - 1;\n        \n        while(evenIndex < A.length && oddIndex > 0)\n        {\n            if(A[evenIndex] % 2 > A[oddIndex] % 2)\n                swap(A, evenIndex, oddIndex);\n            \n            if(A[evenIndex] % 2 == 0) evenIndex += 2;\n            if(A[oddIndex] % 2 == 1)  oddIndex -= 2;\n        }\n        return A;\n    }\n    \n    private void swap(int[] A, int i, int j)\n    {\n        int temp = A[i];\n        A[i] = A[j];\n        A[j] = temp;\n    }\n}\n```
[]