myth
BAN USEROne point which i want to raise in this solution is that you are considering repetition. As i = 0, j = N-1 and k can be 0 and N-1. We can have a[0] + a[N-1] + a[k=0] as 0 which will give us i = 0, j = N-1 and k = 0 which will be a incorrect answer. You have mentioned if condition check for equality in the end which will fail as we will get sum 0 in start.
Otherwise approach seems good to me as it is without extra space.
Another easy to understand solution:
We can see this problem as find pair of elements having a + b = -c. If we can find one pair satisfying this condition, we can say there are three elements having a + b + c = 0;
To solve this problem, we can use hashmap.
Step 1: Store all numbers in a HashMap O(n) time complexity and O(n) space.
Step 2: traverse through our original array and for each element a[i], find (-c - a[i]) element in hashmap which will be done in O(1) time. Total time in this step is O(n) as we need to do this for complete array.
We need to consider c as each and every element so that we can find pairs, so we need to make a loop for c starting from a[0] to a[size-1], which will take O(n) time. We need to skip cth place when running above steps so that we get all numbers seperate.
Total complexity is O(n^2) and space is O(n).
As question is : maximum number of non-intersecting events (not to consider any event which intersect with any other event), in your case you are considering events which are interesting. For example, lets say events are: 1-3, 2-4, 4-6, 6-8, 7-9, 9-10 in sorted order. Then answer should be 4-6 and 9-10. I would like to modify your approach by adding one extra bit which we put with each element in stack.
- myth January 10, 2015Step 1: Sort by starting time.
Step 2: Put first element in stack, when adding next element check if start time of next is in between start and end of top element, then check if take max (end time on top of stack, end time of next). Replace this with end time of top element and mark this as not useful. This will stay on top.
Step 3. When a element comes which is not in the range of top element. Top element is marked, then remove this marked element and add this next element.
For my example:
Step 1: 1-3, not marked
Step 2: 1-4, marked
Step 3: Remove 1-4 and add 4-6.
Step 4: 4-6, 6-8(top) not marked
Step 5: 4-6, 6-9(top) marked
Step 6: 4-6, Remove 6-9 from top and add 9-10 on top.
Step 7. One all are done check if top is marked, if no then we are done, if yes, then remove top.
Now our answer is 4-6 and 9-10.