Java Thought Process - Brute Force + Optimal
After reading the question, it is quite easy to kick-off the Brute Force Solution : \n\n# Brute-Force Solution:\n\n* TC : O(n2)\n* SC : O(1)\n\nclass Solution {
After reading the question, it is quite easy to kick-off the Brute Force Solution : \n\n# Brute-Force Solution:\n```\n* TC : O(n2)\n* SC : O(1)\n\nclass Solution {\n    public int[] minOperations(String boxes) {\n        if(boxes == null || boxes.length()==0) return new int[]{};\n        int n = boxes.length();\n        int[] result = new int[n];\n        \n        for(int i=0;i<n;i++) {\n            for(int j=0;j<n;j++) {\n                if(i!=j && boxes.charAt(j)!=\'0\') {\n                    result[i] += Math.abs(j-i);\n                }\n            }\n        }\n        return result;\n    }\n}\n```\n\n# Optimized Approach :\n\nThe question highlights : \n\n\tthe minimum number of operations needed to move all the balls to the ith box.\n\t\n\t\nSo, if we try to find the number of operations to move all the balls to ith index and that too minimum then we are done.\n\n* Let\'s take two arrays Left[] and Right[] ( why ? -> It is given that we are allowed to move the balls in an adjacent manner so, we will have to levy some space to reduce our time complexity from 10^6 or n2 to a linear solution )\n\nWhen we say calculating the number of operations for moving all the balls to the left of a box to that box, say we are at the ith position(or box). This consists of two parts : \n1. first left[i - 1] will give us the number of operations to move all the balls so far till (i - 1) th position and now we have all the balls till the (i - 1) th position in the (i - 1) th box. \n\n2. The next part involves moving all those balls in (i - 1) th position to the i th position. Also note the cost of moving a single ball by 1 position is 1. Thus, we need to keep in account the number of balls so that we can calculate the cost to move the balls in previous boxes to ith position, as the cost to move a ball in adjacent manner is 1. So, `left[i] = left[i - 1] + (1 * balls)` where 1 here is the cost of moving a single ball in adjacent fashion.\n\n**Note : The number of balls will be used to calculate the number of operations to move the balls at i-1 th index to ith index.**\n\t\n```\nclass Solution {\n    public int[] minOperations(String boxes) {\n        if(boxes == null || boxes.length()==0) return new int[]{};\n        int n = boxes.length();\n        \n        int[] left = new int[n];\n        int[] right = new int[n];\n        int[] result = new int[n];\n        \n        // Left to Right\n        int balls = boxes.charAt(0) == \'1\' ? 1 : 0;\n        for(int i=1;i<n;i++) {\n            left[i] = left[i-1] + 1 * balls;\n            balls += boxes.charAt(i) == \'1\' ? 1 : 0;\n        }\n        \n        // Right to Left\n        balls = boxes.charAt(n-1) == \'1\' ? 1 : 0;\n        for(int i=n-2;i>=0;i--) {\n            right[i] = right[i+1] + 1 * balls;\n            balls += boxes.charAt(i) == \'1\' ? 1 : 0;\n        }\n        \n        for(int i=0;i<n;i++) {\n            result[i] = left[i] + right[i];\n        }\n        return result;\n    }\n}\n\nTC : O(n)\nSC : O(n)\n```\n
['Java']