https://dsa30.vercel.app/_next/static/chunks/pages/day14/practice_…_increasing_subsequence-cfa28f09699afdfd.js

1(self.webpackChunk_N_E=self.webpackChunk_N_E||[]).push([[28088],{4380:(i,s,h)=>{(window.__NEXT_P=window.__NEXT_P||[]).push(["/day14/practice_questions/longest_increasing_subsequence",function(){return h(61658)}])},19941:(i,s,h)=>{"use strict";h.d(s,{P:()=>t});var l=h(37876),e=h(69241),n=h(30087);let r={default:"\uD83D\uDCA1",error:"\uD83D\uDEAB",info:(0,l.jsx)(n.KS,{className:"_mt-1"}),warning:"⚠️"},d={default:(0,e.A)("_border-orange-100 _bg-orange-50 _text-orange-800 dark:_border-orange-400/30 dark:_bg-orange-400/20 dark:_text-orange-300"),error:(0,e.A)("_border-red-200 _bg-red-100 _text-red-900 dark:_border-red-200/30 dark:_bg-red-900/30 dark:_text-red-200"),info:(0,e.A)("_border-blue-200 _bg-blue-100 _text-blue-900 dark:_border-blue-200/30 dark:_bg-blue-900/30 dark:_text-blue-200"),warning:(0,e.A)("_border-yellow-100 _bg-yellow-50 _text-yellow-900 dark:_border-yellow-200/30 dark:_bg-yellow-700/30 dark:_text-yellow-200")};function t({children:i,type:s="default",emoji:h=r[s]}){return(0,l.jsxs)("div",{className:(0,e.A)("nextra-callout _overflow-x-auto _mt-6 _flex _rounded-lg _border _py-2 ltr:_pr-4 rtl:_pl-4","contrast-more:_border-current contrast-more:dark:_border-current",d[s]),children:[(0,l.jsx)("div",{className:"_select-none _text-xl ltr:_pl-3 ltr:_pr-2 rtl:_pr-3 rtl:_pl-2",style:{fontFamily:'"Apple Color Emoji", "Segoe UI Emoji", "Segoe UI Symbol"'},children:h}),(0,l.jsx)("div",{className:"_w-full _min-w-0 _leading-7",children:i})]})}},61658:(i,s,h)=>{"use strict";h.r(s),h.d(s,{Tab:()=>E,default:()=>j,useTOC:()=>x});var l=h(37876),e=h(71807),n=h(69620),r=h(34256),d=h(59095),t=h(19941),a=h(66284),k=h(74338),c=h(30087);let E=d.t.Tab;function x(i){return[{value:(0,l.jsxs)(l.Fragment,{children:["Longest Increasing Subsequence ",(0,l.jsx)(a.H,{level:"medium"})]}),id:"longest-increasing-subsequence-",depth:3},{value:"Description",id:"description",depth:4},{value:"Examples",id:"examples",depth:4},{value:"Constraints",id:"constraints",depth:4},{value:"Try it yourself",id:"try-it-yourself",depth:4},{value:"Solution 1 — O(n\xb2) DP",id:"solution-1--on-dp",depth:4},{value:"Solution 2 — O(n log n) patience sorting",id:"solution-2--on-log-n-patience-sorting",depth:4},{value:"Analysis comparison",id:"analysis-comparison",depth:4}]}let j=(0,e.e)(function(i){let{toc:s=x(i)}=i,h={code:"code",em:"em",h3:"h3",h4:"h4",li:"li",ol:"ol",p:"p",pre:"pre",span:"span",strong:"strong",table:"table",tbody:"tbody",td:"td",th:"th",thead:"thead",tr:"tr",ul:"ul",...(0,r.R)(),...i.components};return(0,l.jsxs)(l.Fragment,{children:[(0,l.jsx)(h.h3,{id:s[0].id,children:s[0].value}),"\n",(0,l.jsx)(h.h4,{id:s[1].id,children:s[1].value}),"\n",(0,l.jsxs)(h.p,{children:["Given an integer array ",(0,l.jsx)(h.code,{children:"nums"}),", return the length of the ",(0,l.jsx)(h.strong,{children:"longest strictly increasing subsequence"}),"."]}),"\n",(0,l.jsxs)(h.p,{children:["A subsequence keeps the relative order of ",(0,l.jsx)(h.code,{children:"nums"})," but can skip arbitrary elements."]}),"\n",(0,l.jsx)(h.h4,{id:s[2].id,children:s[2].value}),"\n",(0,l.jsx)(h.pre,{icon:c.un,tabIndex:"0","data-language":"py","data-word-wrap":"",children:(0,l.jsxs)(h.code,{children:[(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:">"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" Case "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:"1"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:":"})]}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"    nums "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"="}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" ["}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:"10"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:", "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:"9"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:", "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:"2"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:", "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:"5"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:", "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:"3"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:", "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:"7"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:", "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:"101"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:", "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:"18"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"]"})]}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"    Output: "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:"4"})]}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"    Explanation: one "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:"LIS"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:" is"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" ["}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:"2"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:", "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:"3"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:", "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:"7"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:", "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:"101"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"]."})]}),"\n",(0,l.jsx)(h.span,{children:" "}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:">"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" Case "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:"2"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:":"})]}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"    nums "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"="}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" ["}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:"0"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:", "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:"1"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:", "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:"0"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:", "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:"3"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:", "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:"2"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:", "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:"3"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"]"})]}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"    Output: "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:"4"})]}),"\n",(0,l.jsx)(h.span,{children:" "}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:">"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" Case "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:"3"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:":"})]}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"    nums "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"="}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" ["}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:"7"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:", "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:"7"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:", "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:"7"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:", "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:"7"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"]"})]}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"    Output: "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:"1"})]})]})}),"\n",(0,l.jsx)(h.h4,{id:s[3].id,children:s[3].value}),"\n",(0,l.jsxs)(h.ul,{children:["\n",(0,l.jsx)(h.li,{children:(0,l.jsx)(h.code,{children:"1 <= nums.length <= 2500"})}),"\n",(0,l.jsx)(h.li,{children:(0,l.jsx)(h.code,{children:"-10^4 <= nums[i] <= 10^4"})}),"\n",(0,l.jsxs)(h.li,{children:["Follow-up: can you do it in ",(0,l.jsx)(h.code,{children:"O(n log n)"}),"?"]}),"\n"]}),"\n",(0,l.jsx)(h.h4,{id:s[4].id,children:s[4].value}),"\n",(0,l.jsx)(k.v,{title:"Longest Increasing Subsequence — return its length",funcName:"length_of_lis",starter:"def length_of_lis(nums):\n  # dp[i] = longest increasing subsequence ending at i;

1 answer is max(dp)\n  pass",tests:[{args:[[10,9,2,5,3,7,101,18]],expected:4},{args:[[0,1,0,3,2,3]],expected:4},{args:[[7,7,7,7]],expected:1},{args:[[4,10,4,3,8,9]],expected:3},{args:[[1,3,6,7,9,4,10,5,6]],expected:6}],hint:"Let dp[i] be the length of the LIS ending exactly at index i (start each at 1). For every earlier j with nums[j] < nums[i], dp[i] = max(dp[i], dp[j] + 1). Answer is the max over all dp[i].",solution:"def length_of_lis(nums):\n  n = len(nums)\n  dp = [1] * n\n  for i in range(1, n):\n      for j in range(i):\n          if nums[j] < nums[i]:\n              dp[i] = max(dp[i], dp[j] + 1)\n  return max(dp)"}),"\n",(0,l.jsx)(h.h4,{id:s[5].id,children:s[5].value}),"\n",(0,l.jsxs)(h.ol,{children:["\n",(0,l.jsxs)(h.li,{children:[(0,l.jsx)(h.strong,{children:"What am I computing?"})," ",(0,l.jsx)(h.code,{children:"dp[i]"})," = length of the LIS that ",(0,l.jsxs)(h.strong,{children:["ends at index ",(0,l.jsx)(h.code,{children:"i"})]}),"."]}),"\n",(0,l.jsxs)(h.li,{children:[(0,l.jsx)(h.strong,{children:"Dimensions?"})," One."]}),"\n",(0,l.jsxs)(h.li,{children:[(0,l.jsx)(h.strong,{children:"Base cases?"})," ",(0,l.jsx)(h.code,{children:"dp[i] = 1"})," (any single element is an LIS of length 1)."]}),"\n",(0,l.jsxs)(h.li,{children:[(0,l.jsx)(h.strong,{children:"Transition?"})," Look at every earlier ",(0,l.jsx)(h.code,{children:"j"}),". If ",(0,l.jsx)(h.code,{children:"nums[j] < nums[i]"}),", we can extend the LIS that ended at ",(0,l.jsx)(h.code,{children:"j"}),": ",(0,l.jsx)(h.code,{children:"dp[i] = max(dp[i], dp[j] + 1)"}),"."]}),"\n",(0,l.jsxs)(h.li,{children:[(0,l.jsx)(h.strong,{children:"Order?"})," Increasing ",(0,l.jsx)(h.code,{children:"i"}),"."]}),"\n",(0,l.jsxs)(h.li,{children:[(0,l.jsx)(h.strong,{children:"Answer?"})," ",(0,l.jsx)(h.code,{children:"max(dp[i])"})," over all ",(0,l.jsx)(h.code,{children:"i"})," — the LIS doesn’t have to end at the last element."]}),"\n"]}),"\n",(0,l.jsxs)(d.t,{items:["C++","Python","Java"],defaultIndex:"0",children:[(0,l.jsx)(E,{children:(0,l.jsx)(h.pre,{icon:c.z_,tabIndex:"0","data-language":"cpp","data-word-wrap":"","data-copy":"",children:(0,l.jsxs)(h.code,{children:[(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"int"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#6F42C1","--shiki-dark":"#B392F0"},children:" lengthOfLIS"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"("}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#6F42C1","--shiki-dark":"#B392F0"},children:"vector"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"<"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"int"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:">"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"&"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#E36209","--shiki-dark":"#FFAB70"},children:" nums"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:") {"})]}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"    int"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" n "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"="}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" nums."}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#6F42C1","--shiki-dark":"#B392F0"},children:"size"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"();"})]}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"    vector"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"<int>"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#6F42C1","--shiki-dark":"#B392F0"},children:" dp"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"(n, "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:"1"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:");"})]}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"    int"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" best "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"="}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:" 1"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:";"})]}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"    for"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" ("}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"int"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" i "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"="}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:" 1"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"; i "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"<"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" n; i"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"++"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:") {"})]}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"        for"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" ("}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"int"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" j "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"="}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:" 0"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"; j "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"<"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" i; j"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"++"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:") {"})]}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"            if"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" (nums[j] "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"<"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" nums[i]) dp[i] "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"="}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#6F42C1","--shiki-dark":"#B392F0"},children:" max"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"(dp[i], dp[j] "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"+"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:" 1"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:");"})]}),"\n",(0,l.jsx)(h.span,{children:(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"        }"})}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"        best "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"="}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#6F42C1","--shiki-dark":"#B392F0"},children:" max"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"(best, dp[i]);"})]}),"\n",(0,l.jsx)(h.span,{children:(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"    }"})}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"    return"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" best;"})]}),"\n",(0,l.jsx)(h.span,{children:(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"}"})})]})})}),(0,l.jsx)(E,{children:(0,l.jsx)(h.pre,{icon:c.un,tabIndex:"0","data-language":"python","data-word-wrap":"","data-copy":"",children:(0,l.jsxs)(h.code,{children:[(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"def"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#6F42C1","--shiki-dark":"#B392F0"},children:" length_of_lis"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"(nums):"})]}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"    n "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"="}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:" len"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"(nums)"})]}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"    dp "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"="}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" ["}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:"1"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"] "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"*"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" n"})]}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"    for"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" i "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"in"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:" range"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"("}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:"1"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:", n):"})]}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"        for"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" j "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"in"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:" range"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"(i):"})]}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"            if"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" nums[j] "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"<"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" nums[i]:"})]}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"                dp[i] "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"="}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:" max"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"(dp[i], dp[j] "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"+"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:" 1"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:")"})]}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"    return"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:" max"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"(dp)"})]})]})})}),(0,l.jsx)(E,{children:(0,l.jsx)(h.pre,{tabIndex:"0","data-language":"java","data-word-wrap":"","data-copy":"",children:(0,l.jsxs)(h.code,{children:[(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"public"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:" int"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#6F42C1","--shiki-dark":"#B392F0"},children:" lengthOfLIS"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"("}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"int"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"[] nums) {"})]}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"    int"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" n "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"="}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" nums.length;"})]}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"    int"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"[] dp "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"="}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:" new"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:" int"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"[n];"})]}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"    Arrays."}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#6F42C1","--shiki-dark":"#B392F0"},children:"fill"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"(dp, "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:"1"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:");"})]}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"    int"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" best "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"="}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:" 1"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:";"})]}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"    for"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#2

14292E","--shiki-dark":"#E1E4E8"},children:" ("}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"int"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" i "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"="}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:" 1"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"; i "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"<"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" n; i"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"++"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:") {"})]}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"        for"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" ("}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"int"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" j "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"="}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:" 0"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"; j "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"<"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" i; j"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"++"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:") {"})]}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"            if"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" (nums[j] "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"<"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" nums[i]) dp[i] "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"="}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" Math."}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#6F42C1","--shiki-dark":"#B392F0"},children:"max"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"(dp[i], dp[j] "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"+"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:" 1"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:");"})]}),"\n",(0,l.jsx)(h.span,{children:(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"        }"})}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"        best "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"="}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" Math."}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#6F42C1","--shiki-dark":"#B392F0"},children:"max"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"(best, dp[i]);"})]}),"\n",(0,l.jsx)(h.span,{children:(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"    }"})}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"    return"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" best;"})]}),"\n",(0,l.jsx)(h.span,{children:(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"}"})})]})})})]}),"\n",(0,l.jsxs)(h.p,{children:[(0,l.jsx)(h.strong,{children:"Time:"})," ",(0,l.jsx)(h.code,{children:"O(n\xb2)"}),". ",(0,l.jsx)(h.strong,{children:"Space:"})," ",(0,l.jsx)(h.code,{children:"O(n)"}),"."]}),"\n",(0,l.jsx)(h.h4,{id:s[6].id,children:s[6].value}),"\n",(0,l.jsxs)(h.p,{children:["Maintain an array ",(0,l.jsx)(h.code,{children:"tails"}),", where ",(0,l.jsx)(h.code,{children:"tails[k]"})," = the ",(0,l.jsx)(h.strong,{children:"smallest possible tail value"})," of any increasing subsequence of length ",(0,l.jsx)(h.code,{children:"k + 1"}),"."]}),"\n",(0,l.jsxs)(h.p,{children:["For each ",(0,l.jsx)(h.code,{children:"x"})," in ",(0,l.jsx)(h.code,{children:"nums"}),", ",(0,l.jsx)(h.strong,{children:"binary-search"})," for the first ",(0,l.jsx)(h.code,{children:"tails[k] >= x"})," and replace it with ",(0,l.jsx)(h.code,{children:"x"}),". If no such ",(0,l.jsx)(h.code,{children:"k"})," exists, append ",(0,l.jsx)(h.code,{children:"x"})," to extend the longest run by one."]}),"\n",(0,l.jsxs)(h.p,{children:["The length of ",(0,l.jsx)(h.code,{children:"tails"})," at the end is the LIS length."]}),"\n",(0,l.jsx)(t.P,{type:"info",children:(0,l.jsxs)(h.p,{children:[(0,l.jsxs)(h.strong,{children:[(0,l.jsx)(h.code,{children:"tails"})," is not the LIS itself."]})," It’s a clever bookkeeping array. The length of ",(0,l.jsx)(h.code,{children:"tails"})," ",(0,l.jsx)(h.em,{children:"is"}

1)," correct, but the values inside may not form a valid subsequence of ",(0,l.jsx)(h.code,{children:"nums"}),". Reconstructing the actual subsequence requires extra tracking — see “Russian Doll Envelopes” follow-ups."]})}),"\n",(0,l.jsxs)(d.t,{items:["C++","Python","Java"],defaultIndex:"0",children:[(0,l.jsx)(E,{children:(0,l.jsx)(h.pre,{icon:c.z_,tabIndex:"0","data-language":"cpp","data-word-wrap":"","data-copy":"",children:(0,l.jsxs)(h.code,{children:[(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"int"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#6F42C1","--shiki-dark":"#B392F0"},children:" lengthOfLIS"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"("}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#6F42C1","--shiki-dark":"#B392F0"},children:"vector"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"<"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"int"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:">"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"&"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#E36209","--shiki-dark":"#FFAB70"},children:" nums"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:") {"})]}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"    vector"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"<int>"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" tails;"})]}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"    for"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" ("}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"int"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" x : nums) {"})]}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"        auto"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" it "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"="}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#6F42C1","--shiki-dark":"#B392F0"},children:" lower_bound"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"(tails."}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#6F42C1","--shiki-dark":"#B392F0"},children:"begin"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"(), tails."}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#6F42C1","--shiki-dark":"#B392F0"},children:"end"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"(), x);"})]}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"        if"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" (it "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"=="}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" tails."}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#6F42C1","--shiki-dark":"#B392F0"},children:"end"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"()) tails."}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#6F42C1","--shiki-dark":"#B392F0"},children:"push_back"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"(x);"})]}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"        else"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"                   *"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"it "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"="}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" x;"})]}),"\n",(0,l.jsx)(h.span,{children:(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"    }"})}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"    return"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" tails."}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#6F42C1","--shiki-dark":"#B392F0"},children:"size"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"}

1,children:"();"})]}),"\n",(0,l.jsx)(h.span,{children:(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"}"})})]})})}),(0,l.jsx)(E,{children:(0,l.jsx)(h.pre,{icon:c.un,tabIndex:"0","data-language":"python","data-word-wrap":"","data-copy":"",children:(0,l.jsxs)(h.code,{children:[(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"from"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" bisect "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"import"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" bisect_left"})]}),"\n",(0,l.jsx)(h.span,{children:" "}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"def"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#6F42C1","--shiki-dark":"#B392F0"},children:" length_of_lis"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"(nums):"})]}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"    tails "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"="}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" []"})]}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"    for"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" x "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"in"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" nums:"})]}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"        i "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"="}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" bisect_left(tails, x)"})]}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"        if"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" i "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"=="}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:" len"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"(tails): tails.append(x)"})]}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"        else"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:":               tails[i] "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"="}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" x"})]}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"    return"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:" len"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"(tails)"})]})]})})}),(0,l.jsx)(E,{children:(0,l.jsx)(h.pre,{tabIndex:"0","data-language":"java","data-word-wrap":"","data-copy":"",children:(0,l.jsxs)(h.code,{children:[(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"public"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:" int"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#6F42C1","--shiki-dark":"#B392F0"},children:" lengthOfLIS"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"("}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"int"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"[] nums) {"})]}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"    int"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"[] tails "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"="}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:" new"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:" int"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"[nums.length];"})]}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"    int"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" len "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"="}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:" 0"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:";"})]}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"    for"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" ("}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"int"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" x "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:":"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" nums) {"})]}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"        int"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" i "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"="}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" Arrays."}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#6F42C1","--shiki-dark":"#B392F0"},children:"binarySearch"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"(tails, "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:"0"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:", len, x);"})]}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"        if"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" (i "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"<"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:" 0"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:") i "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"="}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:" -"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"(i "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"+"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#005CC5","--shiki-dark":"#79B8FF"},children:" 1"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:");"})]}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"        tails[i] "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"="}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" x;"})]}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"        if"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" (i "}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"=="}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" len) len"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"++"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:";"})]}),"\n",(0,l.jsx)(h.span,{children:(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"    }"})}),"\n",(0,l.jsxs)(h.span,{children:[(0,l.jsx)(h.span,{style:{"--shiki-light":"#D73A49","--shiki-dark":"#F97583"},children:"    return"}),(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:" len;"})]}),"\n",(0,l.jsx)(h.span,{children:(0,l.jsx)(h.span,{style:{"--shiki-light":"#24292E","--shiki-dark":"#E1E4E8"},children:"}"})})]})})})]}),"\n",(0,l.jsxs)(h.p,{children:[(0,l.jsx)(h.strong,{children:"Time:"})," ",(0,l.jsx)(h.code,{children:"O(n log n)"}),". ",(0,l.jsx)(h.strong,{children:"Space:"})," ",(0,l.jsx)(h.code,{children:"O(n)"}),"."]}),"\n",(0,l.jsxs)(h.p,{children:["Why does it work? Replacing ",(0,l.jsx)(h.code,{children:"tails[k]"})," with a smaller value ",(0,l.jsx)(h.code,{children:"x"})," doesn’t shrink any subsequence — it just makes it easier to extend in the future. The invariant (“",(0,l.jsx)(h.code,{children:"tails[k]"})," is the smallest possible tail of any length-",(0,l.jsx)(h.code,{children:"k+1"})," subsequence”) is preserved, and the array’s length only grows when we genuinely found a longer run."]}),"\n",(0,l.jsx)(h.h4,{id:s[7].id,children:s[7].value}),"\n",(0,l.jsxs)(h.table,{children:[(0,l.jsx)(h.thead,{children:(0,l.jsxs)(h.tr,{children:[(0,l.jsx)(h.th,{style:{textAlign:"left"},children:"Approach"}),(0,l.jsx)(h.th,{style:{textAlign:"left"},children:"Time"}),(0,l.jsx)(h.th,{style:{textAlign:"left"},children:"Space"}),(0,l.jsx)(h.th,{style:{textAlign:"left"},children:"When to use"})]})}),(0,l.jsxs)(h.tbody,{children:[(0,l.jsxs)(h.tr,{children:[(0,l.jsxs)(h.td,{style:{textAlign:"left"},children:[(0,l.jsx)(h.code,{children:"O(n\xb2)"})," DP"]}),(0,l.jsx)(h.td,{style:{textAlign:"left"},children:(0,l.jsx)(h.code,{children:"O(n\xb2)"})}),(0,l.jsx)(h.td,{style:{textAlign:"left"},children:(0,l.jsx)(h.code,{children:"O(n)"})}),(0,l.jsxs)(h.td,{style:{textAlign:"left"},children:["Default for small ",(0,l.jsx)(h.code,{children:"n"}),"; easiest to reason about; gives ",(0,l.jsx)(h.code,{children:"dp[i]"})," for free if needed"]})]}),(0,l.jsxs)(h.tr,{children:[(0,l.jsx)(h.td,{style:{textAlign:"left"},children:"Patience sort"}),(0,l.jsx)(h.td,{style:{textAlign:"left"},children:(0,l.jsx)(h.code,{children:"O(n log n)"})}),(0,l.jsx)(h.td,{style:{textAlign:"left"},children:(0,l.jsx)(h.code,{children:"O(n)"})}),(0,l.jsxs)(h.td,{style:{textAlign:"left"},children:["Required for ",(0,l.jsx)(h.code,{children:"n >= ~10^4"}),"; cleaner code; harder to extract actual LIS"]})]})]})]})]})},"/day14/practice_questions/longest_increasing_subsequence",{filePath:"pages/day14/practice_questions/longest_increasing_subsequence.mdx",timestamp:1781490843e3,pageMap:n.O,frontMatter:{},title:"Longest Increasing Subsequence"},"undefined"==typeof RemoteContent?x:RemoteContent.useTOC)},66284:(i,s,h)=>{"use strict";h.d(s,{H:()=>n});var l=h(37876);h(14232);let e={easy:{bg:"#dcfce7",color:"#166534",border:"#bbf7d0"},medium:{bg:"#fef9c3",color:"#854d0e",border:"#fde68a"},hard:{bg:"#fecaca",color:"#991b1b",border:"#fca5a5"}};function n(i){let{level:s}=i,h=e[s.toLowerCase()]||e.easy;return(0,l.jsx)("span",{style:{display:"inline-block",padding:"2px 10px",borderRadius:"12px",fontSize:"12px",fontWeight:600,textTransform:"capitalize",background:h.bg,color:h.color,border:"1px solid ".concat(h.border)},children:s})}}},i=>{i.O(0,[71807,69620,80080,90636,46593,38792],()=>i(i.s=4380)),_N_E=i.O()}]);