## Monday, August 8, 2016

### Google – Partition Array of 0 and 1

Google – Partition Array of 0 and 1

[Solution]
Brute Force, DP
[Solution #1]
Brute Force, 每个位置算左右两边0和1的个数.
O(n^2) time
[Solution #2]
DP，两个数组记录每个位置左边0的个数和右边1的个数。
O(3n) time, O(2n) space
[Solution #3]
DP with space optimization.
space可以优化到O(1), 用两个变量存左边0的个数和右边1的个数。leftZero从0开始，rightOne从(number of ones in the whole array)开始。从左向右扫，碰到0就leftZero++，碰到1就rightOne–.
 `// DP without space optimization` `class` `Solution {` `  ``public` `int` `partitionArray(``int``[] nums) {` `    ``if` `(nums == ``null` `|| nums.length == ``0``) {` `      ``return` `-``1``;` `    ``}` `    `  `    ``int` `n = nums.length;` `    ``int``[] leftZeroes = ``new` `int``[n];` `    ``int``[] rightOnes = ``new` `int``[n];` `    ``leftZeroes[``0``] = nums[``0``] == ``0``? ``1` `: ``0``;` `    ``rightOnes[n - ``1``] = nums[n - ``1``] == ``1``? ``1` `: ``0``;` `    ``for` `(``int` `i = ``1``; i < n; i++) {` `      ``if` `(nums[i] == ``0``) {` `        ``leftZeroes[i] = leftZeroes[i - ``1``] + ``1``;` `      ``}` `      ``else` `{` `        ``leftZeroes[i] = leftZeroes[i - ``1``];` `      ``}` `    ``}` `    `  `    ``for` `(``int` `i = n - ``2``; i >= ``0``; i--) {` `      ``if` `(nums[i] == ``1``) {` `        ``rightOnes[i] = rightOnes[i + ``1``] + ``1``;` `      ``}` `      ``else` `{` `        ``rightOnes[i] = rightOnes[i + ``1``];` `      ``}` `    ``}    ` `    `  `    ``int` `result = ``0``;` `    ``int` `maxSum = ``0``;` `    ``for` `(``int` `i = ``0``; i < n; i++) {` `      ``if` `(leftZeroes[i] + rightOnes[i] > maxSum) {` `        ``maxSum = leftZeroes[i] + rightOnes[i];` `        ``result = i;` `      ``}` `    ``}` `    `  `    ``return` `result;` `  ``}` `}`   `// O(1) space` `class` `Solution2 {` `  ``public` `int` `partitionArray(``int``[] nums) {` `    ``if` `(nums == ``null` `|| nums.length == ``0``) {` `      ``return` `-``1``;` `    ``} ` `    `  `    ``int` `n = nums.length;` `    ``int` `leftZero = ``0``;` `    ``int` `rightOne = ``0``;` `    ``for` `(``int` `i = n - ``1``; i >= ``0``; i--) {` `      ``if` `(nums[i] == ``1``) {` `        ``rightOne++;` `      ``}` `    ``}` `    `  `    ``int` `result = -``1``;` `    ``int` `maxSum = ``0``;` `    ``for` `(``int` `i= ``0``; i < n; i++) {` `      ``if` `(leftZero + rightOne > maxSum) {` `        ``maxSum = leftZero + rightOne;` `        ``result = i;` `      ``}` `      `  `      ``if` `(nums[i] == ``0``) {` `        ``leftZero++;` `      ``}` `      ``else` `{` `        ``rightOne--;` `      ``}` `    ``}` `    `  `    ``return` `result;` `  ``}` `}`