nphardon
BAN USER@varun, your solution does not work at all, it doesn't even address the problem.
Lets use the easiest example: [1,-1,2,-2] on your algo:
countP = 2, countN = 2
scanning input from left to right, 1 is > 0 so output[2] = 1. Increment countN for some reason. Next, -1 > 0 so output[2] = -1. Then increment countP for some reason. You already lost the first 1 in the input by overwriting it in your output.
Your runtime in the comment above is completely wrong.
"so this will take only constant time.(no need to find the minValue and maxValue among K pointers each time since we are already tracking min and max among the K pointers ) "
Every time you move a pointer you are removing minValue and replacing it wiht the new element. Therefore since the previous minValue is "removed" (because you moved the pointer), to find the NEW minvalue, you need to go through all k pointers in the list to see what the new minValue is, which is NOT necessarily the value at your current pointer you just moved. you need to go through and compare again, therefore @xint is correct.
Repsylviarashtons, Accountant at ASAPInfosystemsPvtLtd
I am a journalist. Outside the office, I enjoy additional writing time in a different genre of historical fiction. I ...
the hell is everyone smoking... is everyone reading a different problem or am i? why do all these solutions including this up voted one not even answering the question at all? the sub arrays can start from ANYWHERE in the array, you're not looking for a "split point" to split the array into two... you're looking for two disjoint subarrays. Not sure if everyone is retarded or just me...
- nphardon August 11, 2016