Блог пользователя jaswin6860

Автор jaswin6860, история, 4 дня назад, По-английски

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).

  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится

»
4 дня назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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++.

  • »
    »
    3 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      3 дня назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        3 дня назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?