1
/**
2
 * @param {number[]} nums
3
 * @param {number} k
4
 * @return {number}
5
 */
6
var DoublyLinkedList = function (sum = "DUMMY", index = "DUMMY") {
7
  this.property = { sum, index };
8
  this.prev = null;
9
  this.next = null;
10
};
11

12
DoublyLinkedList.prototype.deque = function () {
13
  const dequeNode = this.next;
14

15
  this.next = dequeNode.next;
16
  dequeNode.next.prev = this;
17

18
  dequeNode.next = null;
19
  dequeNode.prev = null;
20
  return dequeNode;
21
};
22

23
DoublyLinkedList.prototype.pop = function () {
24
  const dequeNode = this.prev;
25

26
  this.prev = dequeNode.prev;
27
  dequeNode.prev.next = this;
28

29
  dequeNode.next = null;
30
  dequeNode.prev = null;
31
  return dequeNode;
32
};
33

34
DoublyLinkedList.prototype.push = function (node) {
35
  const prev = this.prev;
36
  const next = this;
37

38
  node.prev = prev;
39
  node.next = next;
40

41
  prev.next = node;
42
  next.prev = node;
43
};
44

45
var shortestSubarray = function (nums, k) {
46
  // Steps :-
47
  // Initalize 3 vaiables :- sum = 0, subArrayLength = Infinity, queue -> []
48

49
  const dummyHead = new DoublyLinkedList();
50
  const dummyTail = new DoublyLinkedList();
51
  dummyHead.next = dummyTail;
52
  dummyTail.prev = dummyHead;
53

54
  let queueSize = 0;
55

56
  let subArraySize = Number.MAX_SAFE_INTEGER;
57
  let sum = 0;
58
  for (let i = 0; i < nums.length; i++) {
59
    sum += nums[i];
60

61
    // Gives one possible answer, if sum is greater than or
62
    // equal to k
63
    if (sum >= k) subArraySize = Math.min(subArraySize, i + 1);
64

65
    let lastDequeued;
66

67
    // Reduce the queue from left till the sum of elements from
68
    // first index of queue till last index of queue is less than k
69
    // Each time we constantly update the lastdequeued element
70
    // As the last lastdequeued will satisfy sum - lastDequeued.sum >= k
71
    // Thus the range would be i-lastDequeued.property.index
72
    // (without lastDequeued.property.index)
73
    while (queueSize > 0 && sum - dummyHead.next.property.sum >= k) {
74
      queueSize--;
75
      lastDequeued = dummyHead.deque();
76
    }
77

78
    // Using the lastDequeued value to check
79
    if (lastDequeued !== undefined) {
80
      subArraySize = Math.min(subArraySize, i - lastDequeued.property.index);
81
    }
82

83
    // Maintaining the monotonic queue
84
    while (queueSize > 0 && sum <= dummyTail.prev.property.sum) {
85
      queueSize--;
86
      dummyTail.pop();
87
    }
88

89
    const newNode = new DoublyLinkedList(sum, i);
90

91
    dummyTail.push(newNode);
92
    queueSize++;
93
  }
94
  return subArraySize === Number.MAX_SAFE_INTEGER ? -1 : subArraySize;
95
};