Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2407.html

2407. Longest Increasing Subsequence II

  • Difficulty: Hard.
  • Related Topics: .
  • Similar Questions: Longest Increasing Subsequence, Number of Longest Increasing Subsequence, Longest Continuous Increasing Subsequence, Longest Substring of One Repeating Character, Booking Concert Tickets in Groups.

Problem

You are given an integer array nums and an integer k.

Find the longest subsequence of nums that meets the following requirements:

  • The subsequence is strictly increasing and

  • The difference between adjacent elements in the subsequence is at most k.

Return** the length of the longest subsequence that meets the requirements.**

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

  Example 1:

Input: nums = [4,2,1,4,3,4,5,8,15], k = 3
Output: 5
Explanation:
The longest subsequence that meets the requirements is [1,3,4,5,8].
The subsequence has a length of 5, so we return 5.
Note that the subsequence [1,3,4,5,8,15] does not meet the requirements because 15 - 8 = 7 is larger than 3.

Example 2:

Input: nums = [7,4,5,1,8,12,4,7], k = 5
Output: 4
Explanation:
The longest subsequence that meets the requirements is [4,5,8,12].
The subsequence has a length of 4, so we return 4.

Example 3:

Input: nums = [1,5], k = 1
Output: 1
Explanation:
The longest subsequence that meets the requirements is [1].
The subsequence has a length of 1, so we return 1.

  Constraints:

  • 1 <= nums.length <= 105

  • 1 <= nums[i], k <= 105

Solution (Java, C++, Python)

  • class Solution {
        public int lengthOfLIS(int[] nums, int k) {
            SegmentTree root = new SegmentTree(1, 100000);
            int res = 0;
            for (int num : nums) {
                int preMax = root.rangeMaxQuery(root, num - k, num - 1);
                root.update(root, num, preMax + 1);
                res = Math.max(res, preMax + 1);
            }
            return res;
        }
    }
    
    class SegmentTree {
        SegmentTree left, right;
        int start, end, val;
        public SegmentTree(int start, int end) {
            this.start = start;
            this.end = end;
            setup(this, start, end);
        }
        public void setup(SegmentTree node, int start, int end) {
            if (start == end) return;
            int mid = start + (end - start) / 2;
            if (node.left == null) {
                node.left = new SegmentTree(start, mid);
                node.right = new SegmentTree(mid + 1, end);
            }
            setup(node.left, start, mid);
            setup(node.right, mid + 1, end);
            node.val = Math.max(node.left.val, node.right.val);
        }
        
        public void update(SegmentTree node, int index, int val) {
            if (index < node.start || index > node.end) return;
            if (node.start == node.end && node.start == index) {
                node.val = val;
                return;
            }
            update(node.left, index, val);
            update(node.right, index, val);
            node.val = Math.max(node.left.val, node.right.val);
        }
        
        public int rangeMaxQuery(SegmentTree node, int start, int end) {
            if (node.start > end || node.end < start) return 0;
            if (node.start >= start && node.end <= end) return node.val;
            return Math.max(rangeMaxQuery(node.left, start, end), rangeMaxQuery(node.right, start, end));
        }
    }
    
    ############
    
    class Solution {
        public int lengthOfLIS(int[] nums, int k) {
            int mx = nums[0];
            for (int v : nums) {
                mx = Math.max(mx, v);
            }
            SegmentTree tree = new SegmentTree(mx);
            int ans = 0;
            for (int v : nums) {
                int t = tree.query(1, v - k, v - 1) + 1;
                ans = Math.max(ans, t);
                tree.modify(1, v, t);
            }
            return ans;
        }
    }
    
    class Node {
        int l;
        int r;
        int v;
    }
    
    class SegmentTree {
        private Node[] tr;
    
        public SegmentTree(int n) {
            tr = new Node[4 * n];
            for (int i = 0; i < tr.length; ++i) {
                tr[i] = new Node();
            }
            build(1, 1, n);
        }
    
        public void build(int u, int l, int r) {
            tr[u].l = l;
            tr[u].r = r;
            if (l == r) {
                return;
            }
            int mid = (l + r) >> 1;
            build(u << 1, l, mid);
            build(u << 1 | 1, mid + 1, r);
        }
    
        public void modify(int u, int x, int v) {
            if (tr[u].l == x && tr[u].r == x) {
                tr[u].v = v;
                return;
            }
            int mid = (tr[u].l + tr[u].r) >> 1;
            if (x <= mid) {
                modify(u << 1, x, v);
            } else {
                modify(u << 1 | 1, x, v);
            }
            pushup(u);
        }
    
        public void pushup(int u) {
            tr[u].v = Math.max(tr[u << 1].v, tr[u << 1 | 1].v);
        }
    
        public int query(int u, int l, int r) {
            if (tr[u].l >= l && tr[u].r <= r) {
                return tr[u].v;
            }
            int mid = (tr[u].l + tr[u].r) >> 1;
            int v = 0;
            if (l <= mid) {
                v = query(u << 1, l, r);
            }
            if (r > mid) {
                v = Math.max(v, query(u << 1 | 1, l, r));
            }
            return v;
        }
    }
    
  • class Node:
        def __init__(self):
            self.l = 0
            self.r = 0
            self.v = 0
    
    
    class SegmentTree:
        def __init__(self, n):
            self.tr = [Node() for _ in range(4 * n)]
            self.build(1, 1, n)
    
        def build(self, u, l, r):
            self.tr[u].l = l
            self.tr[u].r = r
            if l == r:
                return
            mid = (l + r) >> 1
            self.build(u << 1, l, mid)
            self.build(u << 1 | 1, mid + 1, r)
    
        def modify(self, u, x, v):
            if self.tr[u].l == x and self.tr[u].r == x:
                self.tr[u].v = v
                return
            mid = (self.tr[u].l + self.tr[u].r) >> 1
            if x <= mid:
                self.modify(u << 1, x, v)
            else:
                self.modify(u << 1 | 1, x, v)
            self.pushup(u)
    
        def pushup(self, u):
            self.tr[u].v = max(self.tr[u << 1].v, self.tr[u << 1 | 1].v)
    
        def query(self, u, l, r):
            if self.tr[u].l >= l and self.tr[u].r <= r:
                return self.tr[u].v
            mid = (self.tr[u].l + self.tr[u].r) >> 1
            v = 0
            if l <= mid:
                v = self.query(u << 1, l, r)
            if r > mid:
                v = max(v, self.query(u << 1 | 1, l, r))
            return v
    
    
    class Solution:
        def lengthOfLIS(self, nums: List[int], k: int) -> int:
            tree = SegmentTree(max(nums))
            ans = 1
            for v in nums:
                t = tree.query(1, v - k, v - 1) + 1
                ans = max(ans, t)
                tree.modify(1, v, t)
            return ans
    
    ############
    
    # 2407. Longest Increasing Subsequence II
    # https://leetcode.com/problems/longest-increasing-subsequence-ii
    
    class SegmentTree:
        # https://github.com/cheran-senthil/PyRival/blob/master/pyrival/data_structures/SegmentTree.py
        def __init__(self, data, default=0, func=max):
            """initialize the segment tree with data"""
            self._default = default
            self._func = func
            self._len = len(data)
            self._size = _size = 1 << (self._len - 1).bit_length()
    
            self.data = [default] * (2 * _size)
            self.data[_size:_size + self._len] = data
            for i in reversed(range(_size)):
                self.data[i] = func(self.data[i + i], self.data[i + i + 1])
    
        def __delitem__(self, idx):
            self[idx] = self._default
    
        def __getitem__(self, idx):
            return self.data[idx + self._size]
    
        def __setitem__(self, idx, value):
            idx += self._size
            self.data[idx] = value
            idx >>= 1
            while idx:
                self.data[idx] = self._func(
                    self.data[2 * idx], self.data[2 * idx + 1])
                idx >>= 1
    
        def __len__(self):
            return self._len
    
        def query(self, start, stop):
            """func of data[start, stop)"""
            start += self._size
            stop += self._size
    
            res_left = res_right = self._default
            while start < stop:
                if start & 1:
                    res_left = self._func(res_left, self.data[start])
                    start += 1
                if stop & 1:
                    stop -= 1
                    res_right = self._func(self.data[stop], res_right)
                start >>= 1
                stop >>= 1
    
            return self._func(res_left, res_right)
    
        def __repr__(self):
            return "SegmentTree({0})".format(self.data)
    
    class Solution:
        def lengthOfLIS(self, nums: List[int], k: int) -> int:
            N = len(nums)
            m = max(nums)
            st = SegmentTree([0] * (m + 1))
            res = 1
            
            for x in nums:
                left, right = max(1, x - k), x
                q = st.query(left, right)
                st[x] = 1 + q
                if st[x] > res:
                    res = st[x]
    
            return res
    
    
  • class Node {
    public:
        int l;
        int r;
        int v;
    };
    
    class SegmentTree {
    public:
        vector<Node*> tr;
    
        SegmentTree(int n) {
            tr.resize(4 * n);
            for (int i = 0; i < tr.size(); ++i) tr[i] = new Node();
            build(1, 1, n);
        }
    
        void build(int u, int l, int r) {
            tr[u]->l = l;
            tr[u]->r = r;
            if (l == r) return;
            int mid = (l + r) >> 1;
            build(u << 1, l, mid);
            build(u << 1 | 1, mid + 1, r);
        }
    
        void modify(int u, int x, int v) {
            if (tr[u]->l == x && tr[u]->r == x) {
                tr[u]->v = v;
                return;
            }
            int mid = (tr[u]->l + tr[u]->r) >> 1;
            if (x <= mid)
                modify(u << 1, x, v);
            else
                modify(u << 1 | 1, x, v);
            pushup(u);
        }
    
        void pushup(int u) {
            tr[u]->v = max(tr[u << 1]->v, tr[u << 1 | 1]->v);
        }
    
        int query(int u, int l, int r) {
            if (tr[u]->l >= l && tr[u]->r <= r) return tr[u]->v;
            int mid = (tr[u]->l + tr[u]->r) >> 1;
            int v = 0;
            if (l <= mid) v = query(u << 1, l, r);
            if (r > mid) v = max(v, query(u << 1 | 1, l, r));
            return v;
        }
    };
    
    class Solution {
    public:
        int lengthOfLIS(vector<int>& nums, int k) {
            SegmentTree* tree = new SegmentTree(*max_element(nums.begin(), nums.end()));
            int ans = 1;
            for (int v : nums) {
                int t = tree->query(1, v - k, v - 1) + 1;
                ans = max(ans, t);
                tree->modify(1, v, t);
            }
            return ans;
        }
    };
    
  • func lengthOfLIS(nums []int, k int) int {
    	mx := nums[0]
    	for _, v := range nums {
    		mx = max(mx, v)
    	}
    	tree := newSegmentTree(mx)
    	ans := 1
    	for _, v := range nums {
    		t := tree.query(1, v-k, v-1) + 1
    		ans = max(ans, t)
    		tree.modify(1, v, t)
    	}
    	return ans
    }
    
    type node struct {
    	l int
    	r int
    	v int
    }
    
    type segmentTree struct {
    	tr []*node
    }
    
    func newSegmentTree(n int) *segmentTree {
    	tr := make([]*node, n<<2)
    	for i := range tr {
    		tr[i] = &node{}
    	}
    	t := &segmentTree{tr}
    	t.build(1, 1, n)
    	return t
    }
    
    func (t *segmentTree) build(u, l, r int) {
    	t.tr[u].l, t.tr[u].r = l, r
    	if l == r {
    		return
    	}
    	mid := (l + r) >> 1
    	t.build(u<<1, l, mid)
    	t.build(u<<1|1, mid+1, r)
    	t.pushup(u)
    }
    
    func (t *segmentTree) modify(u, x, v int) {
    	if t.tr[u].l == x && t.tr[u].r == x {
    		t.tr[u].v = v
    		return
    	}
    	mid := (t.tr[u].l + t.tr[u].r) >> 1
    	if x <= mid {
    		t.modify(u<<1, x, v)
    	} else {
    		t.modify(u<<1|1, x, v)
    	}
    	t.pushup(u)
    }
    
    func (t *segmentTree) query(u, l, r int) int {
    	if t.tr[u].l >= l && t.tr[u].r <= r {
    		return t.tr[u].v
    	}
    	mid := (t.tr[u].l + t.tr[u].r) >> 1
    	v := 0
    	if l <= mid {
    		v = t.query(u<<1, l, r)
    	}
    	if r > mid {
    		v = max(v, t.query(u<<1|1, l, r))
    	}
    	return v
    }
    
    func (t *segmentTree) pushup(u int) {
    	t.tr[u].v = max(t.tr[u<<1].v, t.tr[u<<1|1].v)
    }
    
    func max(a, b int) int {
    	if a > b {
    		return a
    	}
    	return b
    }
    

Explain:

nope.

Complexity:

  • Time complexity : O(n).
  • Space complexity : O(n).

All Problems

All Solutions