Linear time solution for this

Question

I was asked this problem during an interview.

You stand at 0 and you need to reach position X. You can jump to D (from 1 to D). If X> D, it is obvious that you cannot reach position X at the initial jump.

Now fragments appear in each cell in random order from 1 to N. This is specified as a zero indexed array A [k], where A [k] represents the position of the tile that appears at the kth second. You have to figure out from what second you can reach (or cross) X's destination.

If this is possible with the initial or after A [0], return 0 or return a minimum of a second. If this is not possible even after all fragments, return -1. A.

Limitations: 1 <= N <= 100000

1 <= D <= 100,000

1 <= X <= 100,000

1 <= A [i] <= X

Eg.

X = 7, D = 3

A = {1,3,1,4,2,5}

then the answer will be 3. Since on the 3rd second the tile appears at position 4, and it becomes possible to reach X = 7. This is impossible any second before that.

I understand that there is too much formulated problem, but I can definitely clarify everything if I can not communicate well.

The trap is that the expected time complexity is O (N), and you can use the extra O (X) space.

I found a solution that is O (n * log n * log n). That is, for a binary search in a second and get the first elements [1..mid], sort them by position and check for a solution. It seemed like he had passed the test tests, but it is not linear.

I tried, but could not find a solution to O (N). could you help me?

Answer 1

By linear you mean a linear number of tiles, right?

If so, this solution (in Java) iterates the array of fragments only once.

In each iteration, it also needs to be repeated D and X times, but it will be linear with respect to the size of the tile array.

Let me know if this looks like what you are looking for.

Note: for simplicity, I assumed that the tile at position “0” becomes available in the second number “0”, therefore it is effective to treat the second “0” as the time when only the tile you are standing on is present, then the remaining tiles appear in seconds 1 , 2, etc.

public class TestTiles { public static int calculateSecond(Integer x, Integer d, int[] tiles) { // start by making all positions unreachable (false) boolean[] posReachable = new boolean[x+1]; // iterate each second only once for (int second = 0; second < tiles.length; second++) { int tile = tiles[second]; // this tile is available now // so mark all positions from "tile" to "tile + d" reachable for (int pos = tile; (pos <= tile + d) && pos <= x; pos++) { posReachable[pos] = true; } // are all positions reachable now? if so, this is the second to return boolean reachable = true; for (int pos = 0; pos <= x; pos++) { reachable &= posReachable[pos]; } if (reachable) return second; } // we can't reach the position return -1; } public static void main(String[] args) { System.out.println(calculateSecond(7, 3, new int[]{0,1,3,1,4,2,5})); System.out.println(calculateSecond(20, 3, new int[]{0,1,3,1,4,2,5})); System.out.println(calculateSecond(2, 3, new int[]{0,1,3,1,4,2,5})); System.out.println(calculateSecond(4, 3, new int[]{0,1,3,1,4,2,5})); System.out.println(calculateSecond(15, 3, new int[]{0,12,3,9,6})); } } 

Answer 2

The following sentence should take O (N * log (min (N, X / D))) time. Please note that this is, in particular, in O (N * log (N)), and therefore has a better rating than the algorithm you proposed or the priority queue algorithm proposed by mcdowella; is in O (N * (X + D)) and therefore has a better rating than the algorithm proposed by eugenioy; does not increase as D increases (as an algorithm of the mcdowella array, eugenia algorithm, and coproc algorithm); and, in addition, for a fixed X it is in O (N).

The idea is to keep the set of intervals that we still need to find the paths. We will save this set in a balanced tree, whose keys are the lower bound of the interval and whose values ​​are the upper bound. When we see a new tile, we will find the interval containing this tile, if any, and divide the interval around the tile, discarding any resulting intervals that are less than D. When our map is empty, we are done.

Haskell follows a full implementation.

 import Data.Ix import Data.Map import qualified Data.Map as M -- setup: the initial set of intervals is just the singleton from 0 to x search :: Int -> Int -> [Int] -> Maybe Int search dx = search_ d (insertCandidate d 0 x empty) search_ :: Int -> Map Int Int -> [Int] -> Maybe Int search_ d = go where -- first base case: we've found all the paths we care about go intervals _ | M.null intervals = Just 0 -- second base case: we're out of tiles, and still don't have all the paths go _ [] = Nothing -- final case: we need to take a time step. add one, and recursively search the remaining time steps go intervals (tile:tiles) = (1+) <$> go newIntervals tiles where newIntervals = case lookupLE tile intervals of Just (lo, hi) | inRange (lo, hi) tile -> insertCandidate d lo tile . insertCandidate d tile hi . delete lo $ intervals _ -> intervals -- only keep non-trivial intervals insertCandidate :: Int -> Int -> Int -> Map Int Int -> Map Int Int insertCandidate d lo hi m | hi - lo <= d = m | otherwise = insert lo hi m 

A few examples of running this in ghci (where I shamelessly plucked examples from another answer):

 > search 3 7 [1,3,1,4,2,5] Just 4 > search 3 20 [1,3,1,4,2,5] Nothing > search 3 2 [1,3,1,4,2,5] Just 0 > search 3 4 [1,3,1,4,2,5] Just 1 > search 3 15 [12,3,9,6] Just 4 

Answer 3

I would look at the tiles one by one, since they are in the array, tracking the largest available position and keeping the priority queue of “waiting” fragments.

• If the tile is larger than X, discard it.
• If the tile is already within the available area, discard it.
• If you cannot reach this tile at the moment, add it to the waiting queue.
• If a tile expands its reach, do it and recycle the nearest tiles in the waiting queue, which are now available or will become available during this processing.
• (If X is now available, stop).

Each fragment is processed no more than two times, at the O (1) stage for processing, except for the cost of adding and removing min from the priority queue of small integers for which specialized algorithms exist - see https://cs.stackexchange.com/questions / 2824 / most-efficient-known-priority-queue-for-inserts .

Answer 4

[This solution in Python is similar to mcdowella; but instead of using the priority queue, he simply uses an array of size X for positions up to X. Its complexity is O(N+min(N,X)*D) , so it is not linear, but linear in N ...]

The world array tracks positions 1, ..., X-1. The current position is updated by each tile, jumping to the farthest available tile.

 def jumpAsFarAsPossible(currentPos, D, X, world): for jump in range(D,0,-1): # jump = D,D-1,...,1 reachablePos = currentPos + jump if reachablePos >= X: return X if world[reachablePos]: return jumpAsFarAsPossible(reachablePos, D, X, world) return currentPos def solve(X,D,A): currentPos = 0 # initially there are no tiles world = X * [False] for k,tilePos in enumerate(A): if tilePos < X: world[tilePos] = True # how far can we move now? if currentPos+D >= tilePos: currentPos = jumpAsFarAsPossible(currentPos, D, X, world) # have we reached X? if currentPos == X: return k # success in k-th second return -1 # X could not be reached 

Answer 5

Here's another try:

Create an array B of size X. Initialize it to MAX_VALUE, and then fill in the elements B [A [i]] = min (B [A [i]], i) so that each element of B is either huge or the first time that a tile appears in the square.

Initialize the current time to zero and work on B from left to right, trying to go from 0 to X with jumping over tiles no more than D, using elements B that do not exceed the current time. If you cannot go further, increase the current time to the minimum value found in any square in B, which allows you to move on.

Cost O (X log (D)) + O (N) - you initialize X with one pass through A of the cost O (N), and then work your way along X one step at a time. If you keep the priority queue for spanning the next elements of D in X at any given time, you can find the smallest reachable element of X at a price of no more than log (D) - and again these are small numbers so you can do better.

Answer 6

My solution is O(N)+O(X/D) . I have two arguments (well, an excuse and a real argument) to protect it as O(N) :

The apology is that I must have O(X) space, and I can't even initialize it to O(N) . Therefore, I assume that the array is pre-initialized, and since my O(X/D) is only the initialization of the array by default, I will gladly ignore it. (Hi, I said that was an excuse).

The real argument is that X/D cannot really be greater than N I mean, if I need to move X positions in steps of no more than D , then each minimum number of steps will be X/D (which means X/D-1 tiles).

• Thus, any problem with X/D-1 > N unsolvable.
• So, the algorithm can start with if (X/D > N+1) return -1 .
• So O(X/D) never greater than O(N) .
• So, O(N)+O(X/D) actually coincides with O(N) .

However, I go with my solution:

Math setting

I will take the “track” with positions 0 to X , so 0 is on the left and X on the right (I need this because I will talk about the “leftmost tile” and the like). The track has X+1 positions numbered from 0 to X First there is a tile at 0 , and the other at X

I split the track into pieces. The fragment size is such that any two adjacent fragments are exactly D The first piece is k , the second is Dk , the third is k , the fourth is Dk again, etc., Moreover, k is something between 1 and D-1 . If D even and we set k=D/2 , all pieces will be equal in size. I feel that the implementation may be a little simpler if k set to 1 and the fragments are processed in pairs, but I really don't know (I did not implement this), and the algorithm is basically the same for any k so I will move on.

The last fragment may be truncated, but I just assume that this is the size that should be, even if it means that it goes beyond X It does not matter. For example, if X=30 , D=13 , k=6 , then there will be 5 pieces with sizes 6-7-6-7-6 (i.e. 0-5 , 6-12 , 13-18 , 19-24 , 25-31 , at 31 , which is not part of the track).

From now on I will use the notation of the array for fragments, i.e. I will refer to the fragment number k as C[k] .

It is very important that two adjacent fragments are always added exactly at position D , because it ensures that:

• If each piece has at least a tile on it, the problem is solved (i.e. no more tiles are needed).
• If there are no tiles on two adjacent pieces, more tiles are required.

If there is a piece that does not fall into any of the previous cases (i.e. one that does not have tiles in it, but the previous and subsequent pieces have tiles), then we need to measure the distance between the leftmost plate in the piece to the right, and the rightmost tile in the piece to the left. If this distance is less than or equal to D , then this piece is not a problem.

To summarize: some pieces are problematic and some are not consistent, according to the following rules:

• A piece with at least one tile on it is never problematic.
• A piece without tiles, and a neighbor (left, right, or both), which also has no tiles, is always problematic.
• A piece C[k] without fragments, with neighbors C[k-1] and C[k+1] with fragments, is problematic if and only if C[k+1].left - C[k-1].right > D

And, the part that jumps into solving the problem:

• We need more fragments to complete the track, if and only if there is at least one problem fragment.

So, the problem regarding the positions of O(X) now deals with no more than O(N) pieces. It's great.

Implementation Details

In an array of pieces, each piece of C[k] will have the following attributes:

• boolean problematic initialized to true .
• integer left initialized to -1 .
• integer right initialized to -1 .

In addition, there will be a problematicCounter initialized by the number of elements in the C array. It will be ticking down when it reaches zero, we know that we no longer need tiles.

The algorithm is as follows:

 if (X/D > N+1) return -1; // Taking care of rounding is left as an exercise Let C = array of chunks as described above For each C[k] // This is the O(X/D) part { Let C[k].problematic = true Let C[k].left = -1 Let C[k].right = -1 } Let problematicCounter = number of elements in array C Let C[k] be the chunk that contains position 0 (usually the first one, but I'll leave open the possibility of "sentinel" chunks) Let C[k].problematic = false Let C[k].left = 0 Let C[k].right = 0 Decrement problematicCounter // The following steps would require tweaking if there is one single chunk on the track // I do not consider that case as that would imply D >= 2*N, which is kind of ridiculous for this problem Let C[k] be the chunk containing position X (the last position on the track) Let C[k].problematic = false Let C[k].left = X Let C[k].right = X Decrease problematicCounter // Initialization done. Now for the loop. // Everything inside the loop is O(1), so the loop itself is O(N) For each A[i] in array A (the array specifying which tile to place in second i) { Let C[k] be the chunk containing position A[i] If C[k].problematic == true { Let C[k].problematic = false; Decrement problematicCounter } If C[k].first == -1 OR C[k].first > A[i] { Let C[k].first = A[i] // Checks that C[k-1] and C[k-2] don't go off array index bounds left as an exercise If C[k-1].problematic == true AND C[k-2].last <> -1 AND C[k].first - C[k-2].last <= D { Let C[k-1].problematic = false Decrement problematicCounter } If C[k].last == -1 OR C[k].last < A[i] { Let C[k].last = A[i] // Checks that C[k+1] and C[k+2] don't go off array index bounds left as an exercise If C[k+1].problematic == true AND C[k+2].first <> -1 AND C[k+2].first - C[k].last <= D { Let C[k+1].problematic = false Decrement problematicCounter } If problematicCounter == 0 Then return k // and forget everything else } return -1