2

Find the subarray of length W which consists of numbers that can be arranged in a continuous sequence. For ex- {4,5,1,5,7,6,8,4,1} and W is 5, output can be -{5,7,6,8,4}..

Bhanu Kishore
  • 59
  • 2
  • Is it homework? If so - please tag it appropriately. What did you try? – amit Sep 02 '12 at 08:36
  • Do you have a limit on the number of numbers in the array? And how do you define continuous sequence? Arithmetic progression with step = 1? – nhahtdh Sep 02 '12 at 08:40
  • I tried the following approach. For every subarray of length W, I will obtain the sum of that subarray. and will subtract W * min(subarray) which must be equal to sum of first W-1 natural numbers. – Bhanu Kishore Sep 02 '12 at 08:44
  • 1
    Yes, the numbers difference should be 1. – Bhanu Kishore Sep 02 '12 at 08:44
  • @BhanuKishore: No, it won't work. The numbers may not form the sequence but still have the sum. – nhahtdh Sep 02 '12 at 08:46
  • 6
    I've removed my answer because OP is too similar to the question from a running contest http://www.codechef.com/SEP12/problems/CHEFTOWN. – Evgeny Kluev Sep 02 '12 at 14:56

1 Answers1

2

A contiguous subarray of length W, containing a continuous (but unsorted) sequence, has three properties that can be used to construct an efficient algorithm:

  1. There are W elements in the subarray.
  2. Difference between max and min numbers in the subarray is W-1.
  3. There are no duplicate elements in the subarray.

Algorithm should advance two pointers to input array and check if the subarray between these pointers satisfies these three properties.

  1. Advance both pointers to keep difference between pointers equal to W.
  2. While advancing the first pointer, put corresponding array element to a set (to control duplicates) and to a min-max queue (to control range of numbers).
  3. If a duplicate is found in the set, advance second pointer to position of first of these duplicate elements, updating both the set and the queue.
  4. Advance second pointer while difference between max and min values keeps greater than W-1, remove corresponding elements from both the set and the queue.
  5. Stop when all three properties are true.

A min-max queue may be implemented as a pair of min-max stacks, described in this answer. A set may be implemented either as a hash set (giving O(n) expected complexity for the algorithm), or as a binary search tree (giving O(n log(n)) worst case complexity), or as a combination of a bitset and a ringbuffer - to keep only bits, corresponding to elements that are between min and max values, reported by queue (giving O(n) worst case complexity).

Example for input array {42,10,7,4,5,1,5,7,6,8,4,1} and W=5 (":" marks start of the ringbuffer).

subarray       bitset        rb_start     min  max
42             :1 0 0 0 0    42           42   42
10             :1 0 0 0 0    10           10   10 (with 42, max-min>W-1)
10 7            1 0:1 0 0    7            7    10
7 4             0 0 1 0:1    4            4    7  (with 10, max-min>W-1)
7 4 5           1 0 1 0:1    4            4    7
4 5 1           1:1 0 0 1    1            1    5  (with 7, max-min>W-1)
1 5             1:1 0 0 0    1            1    5  (5 is a duplicate)
5 7            :1 0 1 0 0    5            5    7  (with 1, max-min>W-1)
5 7 6          :1 1 1 0 0    5            5    7
5 7 6 8        :1 1 1 1 0    5            5    8
5 7 6 8 4       1 1 1 1:1    4            4    8  (success)
Community
  • 1
  • 1
Evgeny Kluev
  • 24,287
  • 7
  • 55
  • 98
  • This is the question from a running contest http://www.codechef.com/SEP12/problems/CHEFTOWN . Please remove your post. Its a humble request – Wayne Rooney Sep 02 '12 at 14:32
  • Contest is over. In fact, contest question is a little bit simpler because it guarantees no duplicates and limits range of array elements. – Evgeny Kluev Sep 11 '12 at 10:14