jaswin6860's blog

Looking for an alternative solution apart from brute force
By jaswin6860, history, 3 days ago, In English

I wanted to ask an idea to solve the question. But couldn't find the right place so posting it here, In a hope to get an answer from someone.

Find longest valid subarray in the orders array.

  1. Each order can be delivered or picked once.
  2. Delivery can only happen after pick up.

Ex 1: orders = ['P1', 'P1', 'D1'], return ['P1', 'D1'] Ex 2: orders = ['P1', 'P1', 'D1', 'D1'], return ['P1', 'D1'] Ex 3: orders = ['P1', 'P2' , 'P3', 'D2', 'D3'] return ['P2', 'P3', 'D2', 'D3']

How can we solve this? I could not think of a better solution than brute force which is O(n^3).

  • Vote: I like it
  • -2
  • Vote: I do not like it

»
3 days ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I think you can solve that in nearly O(n) by using two maps. This is kind of two pointer approach. First keep ith pointer at 0th index and jth pointer in 1st index and start checking. First when you found a new picked order you have to include that in a map. When you find a delivery order first check whether that order available in your map if so reduce that order from the map and store the current delivery number and picked order number in an another map(let's called it y). At the same time you have to keep a variable which stores the current valid subarray from ith pointher to jth pointer and then do j++. If that order doesn't available you just need to check whether current subarray is longer than the previous ones. If so you have to iterate through the i th pointer to jth pointer and check those orders available in the y map and if so include them in a new vector and store. and then move i pointer to jth pointer and do j++.

→ Reply
  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    While I appreciate your response, Can you please provide pseudo code for better understanding? This comment is going over my head :(

    → Reply
    • »
      »
      »
      3 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you send me the problem link I'll send my submission

      → Reply
      • »
        »
        »
        »
        3 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I couldn't find this problem anywhere. And I don't think this problem is listed anywhere. But I do have some test cases with answers which I got using brute force approach.

        → Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

is this not solvable in O(n)? Just do sliding window and keep track of which delivery/order was picked up using vectors, and keep track of the maximum window you've seen. When encountering an invalid item, keep closing the window until its valid (or start a new window from next index if it could never become valid). The result is maximum valid window youve seen

→ Reply
  • »
    »
    2 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How will you decrease your valid window in case of [P11, D11, P11, P12, P11, D12, D11] when your jth index is at 4 and 5?

    → Reply