sachaudh
BAN USERLets say you have an array A = **###***#**##*###*#* and you have another array B.
Step 1: What you can do is go through array A and where a sequence of either * or # starts at index i, place how many are in that sequence at the index i in array B. In this case you'd have something like 20300300120201300111, where each non-zero value is the number of * or # in a sequence starting at that index i in array A.
Step 2: Now go through B using two pointers: x and y. You are only comparing non-zero values. make x point to the first non-zero value and have y be the next one over. if they are equal, save the index and value of x. Now make x point to y and iterate y again to the next one. if that value isn't greater than the one you saved, don't overwrite your saved index and value. keep going to the end. you'll have the index of the start of the sequence and how large it is (where the value you saved should be doubled, since it accounts for only either *'s or #'s not the full sequence of *'s and #'s)
It takes O(N) for Step 1, and O(N) for Step 2, which is O(2N) = O(N) runtime overall. You have O(N) space as well for the array you make.
So this only works when there are no doubles of an element next to each other. For example, 0122022111 would end up as 0012222111 at some point with the current pointer pointing at the last 2. You would need to make 1 go before the 2's, but if you just swap then you would get 0012221211. So you might have to have an extra pointer that keeps track of the last 1 while ordering, so 0012222111 would have the extra pointer point at the 1 before the 2. So whenever you get a 1, then just place it after the last 1 in the order.
If it was a doubly-linked list, then you could always just have 0's point to the head and 2's be the successor of the last element. and pass by 1's. If it is a singly linked list, then you would need a different method.
I tried using an example. Tell me if I got it. You have a linked list that looks like this: [0] --> [1] --> [2] --> [1] --> [2] --> [0] for example. You start at [0] and compare to the next node [1]. since 0 <= 1, you move on. You compare [1] to the next node [2]. 1 <= 2, so you move on. You compare [2] to the next node [1]. 2 <= 1 is not true, so you make [2] point to [1]'s successor and make [1] point to [2]. Now you have [0] --> [1] --> [1] --> [2] --> [2] --> [0]. Continue by comparing [2] to the next node [2]. since 2 <= 2, you move on. Compare [2] to the next node [0]. since 2 <= 0 is not true and the next node is 0, make [0] point to the head node, and make [2] point to [0]'s successor (which is null). You finally have [0] --> [0] --> [1] --> [1] --> [2] --> [2]. And you are done. Let me know if you find some error with this process.
- sachaudh September 12, 2012
Lets say you have an array A = **###***#**##*###*#* and you have another array B.
- sachaudh August 04, 2014Step 1: What you can do is go through array A and where a sequence of either * or # starts at index i, place how many are in that sequence at the index i in array B. In this case you'd have something like 20300300120201300111, where each non-zero value is the number of * or # in a sequence starting at that index i in array A.
Step 2: Now go through B using two pointers: x and y. You are only comparing non-zero values. make x point to the first non-zero value and have y be the next one over. if they are equal, save the index and value of x. Now make x point to y and iterate y again to the next one. if that value isn't greater than the one you saved, don't overwrite your saved index and value. keep going to the end. you'll have the index of the start of the sequence and the length / 2 (just double it)
It takes O(N) for Step 1, and O(N) for Step 2, which is O(2N) = O(N) runtime overall. You have O(N) space as well for the array you make.