var Component=(()=>{var S=Object.create;var u=Object.defineProperty;var I=Object.getOwnPropertyDescriptor;var N=Object.getOwnPropertyNames;var q=Object.getPrototypeOf,C=Object.prototype.hasOwnProperty;var w=i=>u(i,"__esModule",{value:!0});var T=(i,r)=>()=>(r||i((r={exports:{}}).exports,r),r.exports),j=(i,r)=>{w(i);for(var s in r)u(i,s,{get:r[s],enumerable:!0})},P=(i,r,s)=>{if(r&&typeof r=="object"||typeof r=="function")for(let n of N(r))!C.call(i,n)&&n!=="default"&&u(i,n,{get:()=>r[n],enumerable:!(s=I(r,n))||s.enumerable});return i},O=i=>P(w(u(i!=null?S(q(i)):{},"default",i&&i.__esModule&&"default"in i?{get:()=>i.default,enumerable:!0}:{value:i,enumerable:!0})),i);var k=T((L,v)=>{v.exports=_jsx_runtime});var M={};j(M,{Highlight:()=>d,default:()=>E,frontmatter:()=>A});var e=O(k()),A={title:"Arrays",date:"2024-11-17",lastmod:"2026-07-31",tags:["Algorithms","array"],draft:!1,summary:"2 Problems",images:[],layout:"QuestionsPostLayout",readTime:"2 Popular Problems",canonicalUrl:"https://codewithlucian.com/coding/arrays",thumbnail:"/static/images/codingInterview/arrays2.svg"},d=({children:i,color:r})=>(0,e.jsx)("span",{style:{backgroundColor:r,borderRadius:"2px",color:"#fff",padding:"0.2rem"},children:i});function z(i={}){let{wrapper:r}=i.components||{};return r?(0,e.jsx)(r,Object.assign({},i,{children:(0,e.jsx)(s,{})})):s();function s(){let n=Object.assign({section:"section",p:"p",h2:"h2",a:"a",span:"span",strong:"strong",h4:"h4",code:"code",hr:"hr",h3:"h3",ul:"ul",li:"li",pre:"pre",ol:"ol",blockquote:"blockquote"},i.components),{ProgressProvider:f,ProgressWrapper:g,TopicScope:y,SimpleCollapsibleSection:o,SimpleSectionTitle:c,TextContainer:l,Image:x,CollapsibleQuestionsWrapper:b,CollapsibleSection:p,SectionTitle:m,TabItem:t,Tabs:h}=n;return b||a("CollapsibleQuestionsWrapper",!0),p||a("CollapsibleSection",!0),x||a("Image",!0),f||a("ProgressProvider",!0),g||a("ProgressWrapper",!0),m||a("SectionTitle",!0),o||a("SimpleCollapsibleSection",!0),c||a("SimpleSectionTitle",!0),t||a("TabItem",!0),h||a("Tabs",!0),l||a("TextContainer",!0),y||a("TopicScope",!0),(0,e.jsxs)(n.section,{className:"h0Wrapper headingWrapper",children:[" "," ",(0,e.jsxs)(f,{slug:"arrays",children:[(0,e.jsx)(g,{}),(0,e.jsx)(y,{children:(0,e.jsx)(n.p,{children:"Covers array fundamentals and the existing guided problems, focusing on indexing, traversal, transformations, and the time and space tradeoffs used to reason about array solutions."})}),(0,e.jsxs)(n.h2,{id:"theory",children:[(0,e.jsx)(n.a,{href:"#theory","aria-hidden":"true",tabIndex:"-1",children:(0,e.jsx)(n.span,{className:"icon icon-link"})}),"Theory"]}),(0,e.jsxs)(o,{children:[(0,e.jsxs)(c,{children:["What is an ",(0,e.jsx)(n.strong,{children:"Array"}),"?"]}),(0,e.jsxs)(l,{children:[(0,e.jsxs)(n.h4,{id:"definition",children:[(0,e.jsx)(n.a,{href:"#definition","aria-hidden":"true",tabIndex:"-1",children:(0,e.jsx)(n.span,{className:"icon icon-link"})}),"Definition"]}),(0,e.jsxs)(n.p,{children:["An ",(0,e.jsx)(n.strong,{children:"array"})," is a data structure that stores a fixed-size, ordered collection of elements of the same type."]}),(0,e.jsxs)(n.p,{children:["It provides a way to store multiple values under a single name, where each element can be accessed directly using its ",(0,e.jsx)(n.code,{children:"index"}),"."]}),(0,e.jsx)(n.hr,{})]})]}),(0,e.jsxs)(o,{children:[(0,e.jsx)(c,{children:"How does it work?"}),(0,e.jsxs)(l,{children:[(0,e.jsxs)(n.h3,{id:"how-arrays-work-internally",children:[(0,e.jsx)(n.a,{href:"#how-arrays-work-internally","aria-hidden":"true",tabIndex:"-1",children:(0,e.jsx)(n.span,{className:"icon icon-link"})}),(0,e.jsx)(n.strong,{children:"How Arrays Work Internally"})]}),(0,e.jsxs)(n.h4,{id:"1-index-based-access",children:[(0,e.jsx)(n.a,{href:"#1-index-based-access","aria-hidden":"true",tabIndex:"-1",children:(0,e.jsx)(n.span,{className:"icon icon-link"})}),"1. ",(0,e.jsx)(n.strong,{children:"Index-Based Access"})]}),(0,e.jsxs)(n.ul,{children:[(0,e.jsx)(n.li,{children:"Arrays use zero-based indexing."}),(0,e.jsx)(n.li,{children:"To access an element, the memory address is computed as:"})]}),(0,e.jsx)(n.pre,{className:"language-java",children:(0,e.jsx)(n.code,{className:"language-java code-highlight",children:(0,e.jsxs)(n.span,{className:"code-line",children:[" ",(0,e.jsx)(n.span,{className:"token class-name",children:"Address"})," ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," ",(0,e.jsx)(n.span,{className:"token class-name",children:"Base"}),"\xA0",(0,e.jsx)(n.span,{className:"token class-name",children:"Address"})," ",(0,e.jsx)(n.span,{className:"token operator",children:"+"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),(0,e.jsx)(n.span,{className:"token class-name",children:"Index"})," \xD7 ",(0,e.jsx)(n.span,{className:"token class-name",children:"Element"}),"\xA0",(0,e.jsx)(n.span,{className:"token class-name",children:"Size"}),(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),` `]})})}),(0,e.jsx)(n.ul,{children:(0,e.jsxs)(n.li,{children:["This makes element access ",(0,e.jsx)(n.code,{children:"O(1)"}),", as the index is directly mapped to a memory location."]})}),(0,e.jsxs)(n.h4,{id:"2-contiguous-memory-allocation",children:[(0,e.jsx)(n.a,{href:"#2-contiguous-memory-allocation","aria-hidden":"true",tabIndex:"-1",children:(0,e.jsx)(n.span,{className:"icon icon-link"})}),"2. ",(0,e.jsx)(n.strong,{children:"Contiguous Memory Allocation"})]}),(0,e.jsxs)(n.ul,{children:[(0,e.jsx)(n.li,{children:"Arrays are stored in contiguous memory locations in RAM."}),(0,e.jsx)(n.li,{children:"Each element occupies a fixed number of bytes based on the data type (e.g., 4 bytes for integers in many systems)."})]}),(0,e.jsxs)("div",{className:"flex flex-wrap",children:[(0,e.jsx)("span",{className:"flex flex-wrap m-2 ml-6 p-2"}),(0,e.jsx)(x,{alt:"arrays",src:"/static/images/codingInterview/arrays.svg",className:"flex flex-wrap m-2 ml-10 p-2",width:450,height:300})]}),(0,e.jsxs)(n.h3,{id:"what-happens-when-an-arrays-size-is-reached",children:[(0,e.jsx)(n.a,{href:"#what-happens-when-an-arrays-size-is-reached","aria-hidden":"true",tabIndex:"-1",children:(0,e.jsx)(n.span,{className:"icon icon-link"})}),(0,e.jsx)(n.strong,{children:"What Happens When an Array's Size is Reached?"})]}),(0,e.jsxs)(n.ol,{children:[(0,e.jsxs)(n.li,{children:[(0,e.jsx)(n.p,{children:(0,e.jsx)(n.strong,{children:"Fixed-Size Limitation"})}),(0,e.jsx)(n.ul,{children:(0,e.jsx)(n.li,{children:"In most programming languages, a low-level array has a fixed size. If the size is reached, no more elements can be added."})})]}),(0,e.jsxs)(n.li,{children:[(0,e.jsx)(n.p,{children:(0,e.jsx)(n.strong,{children:"Dynamic Resizing"})}),(0,e.jsxs)(n.ul,{children:[(0,e.jsxs)(n.li,{children:["Languages like ",(0,e.jsx)(n.strong,{children:"Python"})," (",(0,e.jsx)(n.code,{children:"list"}),"), ",(0,e.jsx)(n.strong,{children:"Java"})," (",(0,e.jsx)(n.code,{children:"ArrayList"}),"), ",(0,e.jsx)(n.strong,{children:"C#"})," (",(0,e.jsx)(n.code,{children:"List"}),"), and ",(0,e.jsx)(n.strong,{children:"JavaScript"})," (",(0,e.jsx)(n.code,{children:"Array"}),") provide abstractions over arrays that resize dynamically when their capacity is exceeded."]}),(0,e.jsxs)(n.li,{children:["Internally, these dynamic data structures create a ",(0,e.jsx)(n.strong,{children:"new array"})," with a larger size and copy existing elements into it."]})]})]})]}),(0,e.jsx)(n.hr,{}),(0,e.jsxs)(n.h3,{id:"dynamic-resizing-process",children:[(0,e.jsx)(n.a,{href:"#dynamic-resizing-process","aria-hidden":"true",tabIndex:"-1",children:(0,e.jsx)(n.span,{className:"icon icon-link"})}),(0,e.jsx)(n.strong,{children:"Dynamic Resizing Process"})]}),(0,e.jsxs)(n.ol,{children:[(0,e.jsxs)(n.li,{children:[(0,e.jsxs)(n.p,{children:[(0,e.jsx)(n.strong,{children:"Capacity Doubling"}),":"]}),(0,e.jsxs)(n.ul,{children:[(0,e.jsxs)(n.li,{children:["When the array reaches its maximum size, a new array is created with double the current capacity (in most implementations). For example:",(0,e.jsx)(n.ul,{children:(0,e.jsx)(n.li,{children:"If the array size is 4 and a 5th element is added, a new array of size 8 is created."})})]}),(0,e.jsx)(n.li,{children:"This provides (O(1)) amortized cost for insertions, as resizing happens infrequently."})]})]}),(0,e.jsxs)(n.li,{children:[(0,e.jsxs)(n.p,{children:[(0,e.jsx)(n.strong,{children:"Copying Elements"}),":"]}),(0,e.jsxs)(n.ul,{children:[(0,e.jsx)(n.li,{children:"Existing elements are copied from the old array to the new array."}),(0,e.jsx)(n.li,{children:"This copying process takes (O(n)) time, where (n) is the number of elements."})]})]}),(0,e.jsxs)(n.li,{children:[(0,e.jsxs)(n.p,{children:[(0,e.jsx)(n.strong,{children:"Updating the Reference"}),":"]}),(0,e.jsx)(n.ul,{children:(0,e.jsx)(n.li,{children:"The old array reference is updated to point to the new array."})})]})]}),(0,e.jsx)(n.hr,{})]})]}),(0,e.jsxs)(n.h2,{id:"coding",children:[(0,e.jsx)(n.a,{href:"#coding","aria-hidden":"true",tabIndex:"-1",children:(0,e.jsx)(n.span,{className:"icon icon-link"})}),"Coding"]}),(0,e.jsxs)(b,{children:[(0,e.jsxs)(p,{difficulty:"junior",questionId:"arrays-q1-contains-duplicate",children:[(0,e.jsx)(m,{children:"Q1 - Contains Duplicate"}),(0,e.jsxs)(l,{children:[(0,e.jsx)(d,{color:"rgb(34 197 94)",children:"Easy Difficulty"}),(0,e.jsx)(n.blockquote,{children:(0,e.jsxs)(n.p,{children:["Given an integer array ",(0,e.jsx)(n.code,{children:"nums"}),", return ",(0,e.jsx)(n.code,{children:"true"})," if any value appears more than once in the array, otherwise return ",(0,e.jsx)(n.code,{children:"false"}),"."]})}),(0,e.jsx)(t,{label:"java",language:"javascript",code:`// Example 1: Input: nums = [1, 2, 3, 3] Output: true // Example 2: Input: nums = [1, 2, 3, 4] Output: false`}),(0,e.jsx)(n.hr,{}),(0,e.jsxs)("details",{children:[(0,e.jsx)("summary",{children:(0,e.jsx)(n.strong,{children:"_ Hint 1"})}),(0,e.jsx)(n.ul,{children:(0,e.jsx)(n.li,{children:"A brute force solution would be to check every element against every other element in the array. This would be an O(n^2) solution. Can you think of a better way?"})})]}),(0,e.jsxs)("details",{children:[(0,e.jsx)("summary",{children:(0,e.jsx)(n.strong,{children:"_ Hint 2"})}),(0,e.jsxs)(n.ul,{children:[(0,e.jsx)(n.li,{children:"First we can sort the input list to rearrange the elements in ascending order."}),(0,e.jsx)(n.li,{children:"After sorting, we iterates through the list and checks if adjacent elements are equal."})]})]}),(0,e.jsx)(n.hr,{})]})]}),(0,e.jsxs)(p,{difficulty:"mid-level",questionId:"arrays-q2-product-of-array-except-self",children:[(0,e.jsx)(m,{children:"Q2 - Product of Array Except Self"}),(0,e.jsxs)(l,{children:[(0,e.jsx)(d,{color:"rgb(202 138 4)",children:"Medium Difficulty"}),(0,e.jsxs)(n.blockquote,{children:[(0,e.jsxs)(n.p,{children:["Given an integer array ",(0,e.jsx)(n.code,{children:"nums"}),", return an array answer such that ",(0,e.jsx)(n.code,{children:"answer[i]"})," is equal to the product of all the elements of nums except ",(0,e.jsx)(n.code,{children:"nums[i]"}),"."]}),(0,e.jsx)(n.p,{children:"The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer."}),(0,e.jsxs)(n.p,{children:["You must write an algorithm that runs in ",(0,e.jsx)(n.code,{children:"O(n)"})," time and without using the division operation."]})]}),(0,e.jsx)(n.p,{children:(0,e.jsx)(n.strong,{children:"Example 1:"})}),(0,e.jsx)(t,{label:"java",language:"javascript",code:`//Example 1: Input: nums = [1,2,3,4] Output: [24,12,8,6] //Example 2: Input: nums = [-1,1,0,-3,3] Output: [0,0,9,0,0]`}),(0,e.jsx)(n.hr,{}),(0,e.jsxs)(n.h3,{id:"hints",children:[(0,e.jsx)(n.a,{href:"#hints","aria-hidden":"true",tabIndex:"-1",children:(0,e.jsx)(n.span,{className:"icon icon-link"})}),(0,e.jsx)(n.strong,{children:"Hints"})]}),(0,e.jsxs)("details",{children:[(0,e.jsx)("summary",{children:(0,e.jsx)(n.strong,{children:"_ Hint 1"})}),(0,e.jsx)(n.p,{children:"A brute-force solution would be to iterate through the array with index i and compute the product of the array except for that index element."}),(0,e.jsxs)(n.p,{children:["This would be an ",(0,e.jsx)(n.code,{children:"O(n^2"}),") solution. Can you think of a better way?"]})]}),(0,e.jsxs)("details",{children:[(0,e.jsx)("summary",{children:(0,e.jsx)(n.strong,{children:"_ Hint 2"})}),(0,e.jsx)(n.p,{children:"We can use the prefix and suffix technique."}),(0,e.jsxs)(n.ul,{children:[(0,e.jsx)(n.li,{children:"First, we iterate from left to right and store the prefix products for each index in a prefix array, excluding the current index's number."}),(0,e.jsx)(n.li,{children:"Then, we iterate from right to left and store the suffix products for each index in a suffix array, also excluding the current index's number."})]})]}),(0,e.jsx)(n.hr,{})]})]}),(0,e.jsxs)(o,{children:[(0,e.jsx)(c,{children:"Reference: Top K Frequent Elements"}),(0,e.jsxs)(l,{children:[(0,e.jsxs)(n.p,{children:["This problem belongs to the HashMaps topic. ",(0,e.jsx)(n.a,{href:"/coding/hashing",children:"Open the canonical question and solution"}),"."]}),(0,e.jsx)(d,{color:"rgb(202 138 4)",children:"Medium Difficulty"}),(0,e.jsx)(n.blockquote,{children:(0,e.jsxs)(n.p,{children:["Given an integer array ",(0,e.jsx)(n.code,{children:"nums"})," and an integer ",(0,e.jsx)(n.code,{children:"k"}),", return the k most frequent elements. You may return the answer in any order."]})}),(0,e.jsx)(n.p,{children:(0,e.jsx)(n.strong,{children:"Example 1:"})}),(0,e.jsx)(t,{label:"java",language:"javascript",code:`Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2]`}),(0,e.jsx)(n.p,{children:(0,e.jsx)(n.strong,{children:"Example 2:"})}),(0,e.jsx)(t,{label:"java",language:"javascript",code:`Input: nums = [7,7], k = 1 Output: [7]`}),(0,e.jsx)(n.hr,{}),(0,e.jsxs)("details",{children:[(0,e.jsx)("summary",{children:(0,e.jsx)(n.strong,{children:"_ Hint 1"})}),(0,e.jsxs)(n.p,{children:[(0,e.jsx)(d,{color:"#25c2a0",children:"Create a hashmap"})," to store the frequency of each element in the input array."]})]}),(0,e.jsxs)("details",{children:[(0,e.jsx)("summary",{children:(0,e.jsx)(n.strong,{children:"_ Hint 2"})}),(0,e.jsx)(n.p,{children:"Convert the hashmap items into pairs and store them in a list (pairs)."})]}),(0,e.jsxs)("details",{children:[(0,e.jsx)("summary",{children:(0,e.jsx)(n.strong,{children:"_ Hint 3"})}),(0,e.jsxs)(n.p,{children:[(0,e.jsx)(d,{color:"#1877F2",children:"Sort the list of pairs"})," based on the frequency in descending order."]})]}),(0,e.jsxs)(n.p,{children:[(0,e.jsx)(n.strong,{children:"Move to solution:"})," ",(0,e.jsx)(n.a,{href:"#solution-Q3",children:"Solution Q3 - Top K Frequent Elements"}),"."]}),(0,e.jsx)(n.hr,{})]})]}),(0,e.jsxs)(n.h2,{id:"solutions",children:[(0,e.jsx)(n.a,{href:"#solutions","aria-hidden":"true",tabIndex:"-1",children:(0,e.jsx)(n.span,{className:"icon icon-link"})}),"Solutions"]}),(0,e.jsxs)(o,{children:[(0,e.jsx)(c,{children:"Solution Q1"}),(0,e.jsxs)(l,{children:[(0,e.jsx)(n.p,{children:(0,e.jsx)(n.strong,{children:"Solution Overview:"})}),(0,e.jsxs)(n.ol,{children:[(0,e.jsx)(n.li,{children:"The solution first sorts the input list, which rearranges the elements in ascending order."}),(0,e.jsx)(n.li,{children:"After sorting, it iterates through the list and checks if adjacent elements are equal."}),(0,e.jsx)(n.li,{children:"If it finds any equal adjacent elements, it returns True, indicating that a duplicate exists. If the loop completes without finding any duplicates, it returns False."})]}),(0,e.jsx)(n.p,{children:(0,e.jsx)(n.strong,{children:"Time Complexity:"})}),(0,e.jsx)(n.ul,{children:(0,e.jsxs)(n.li,{children:[(0,e.jsx)(n.code,{children:"O(NlogN)"})," The time complexity of this solution is dominated by the sorting step, which is typically",(0,e.jsx)(n.code,{children:"O(NlogN)"})]})}),(0,e.jsx)(n.p,{children:(0,e.jsx)(n.strong,{children:"Space Complexity:"})}),(0,e.jsx)(n.ul,{children:(0,e.jsxs)(n.li,{children:[(0,e.jsx)(n.code,{children:"O(N)"})," because the code sorts the input list in place, and it does not use additional data structures that grow with the input size."]})}),(0,e.jsxs)(n.h4,{id:"code-solution",children:[(0,e.jsx)(n.a,{href:"#code-solution","aria-hidden":"true",tabIndex:"-1",children:(0,e.jsx)(n.span,{className:"icon icon-link"})}),"Code Solution"]}),(0,e.jsxs)(h,{children:[(0,e.jsx)(t,{label:"Python",language:"python",code:`def containsDuplicate(self, nums: List[int]) -> bool: nums.sort() for i in range(len(nums)-1): if nums[i] == nums[i+1]: return True return False`}),(0,e.jsx)(t,{label:"Javascript",language:"javascript",code:`var containsDuplicate = function(nums) { nums.sort((a, b) => a - b); for (let i = 0; i < nums.length - 1; i++) { if (nums[i] === nums[i + 1]) { return true; } } return false; };`}),(0,e.jsx)(t,{label:"Java",language:"javascript",code:`public boolean containsDuplicate(int[] nums) { Arrays.sort(nums); for (int i = 0; i < nums.length - 1; i++) { if (nums[i] == nums[i + 1]) { return true; } } return false; }`})]}),(0,e.jsx)(n.hr,{})]})]}),(0,e.jsxs)(o,{children:[(0,e.jsx)(c,{children:"Solution Q2"}),(0,e.jsxs)(l,{children:[(0,e.jsx)(n.p,{children:(0,e.jsx)(n.strong,{children:"Solution Overview:"})}),(0,e.jsxs)(n.ol,{children:[(0,e.jsx)(n.li,{children:"We start by initializing an array result to store the final product values."}),(0,e.jsx)(n.li,{children:"We first calculate the prefix products while iterating through the input array from left to right. For each element, we update result with the prefix product up to that point, and we update prefix_product by multiplying it with the current element."}),(0,e.jsx)(n.li,{children:"Next, we calculate the postfix products while iterating through the input array from right to left. We update result by multiplying it with the postfix product for each element, and we update postfix_product in a similar manner."}),(0,e.jsx)(n.li,{children:"The final result array contains the product of all elements except the element itself, achieved by combining the prefix and postfix products."})]}),(0,e.jsx)(n.p,{children:(0,e.jsx)(n.strong,{children:"Time Complexity:"})}),(0,e.jsx)(n.ul,{children:(0,e.jsxs)(n.li,{children:[(0,e.jsx)(n.code,{children:"O(N)"}),", because we iterate through the array twice, once for calculating the prefix products and once for calculating the postfix products."]})}),(0,e.jsx)(n.p,{children:(0,e.jsx)(n.strong,{children:"Space Complexity:"})}),(0,e.jsx)(n.ul,{children:(0,e.jsxs)(n.li,{children:[(0,e.jsx)(n.code,{children:"O(1)"})," because we don't use any extra space that grows with the input size. T"]})}),(0,e.jsxs)(n.h4,{id:"code-solution-1",children:[(0,e.jsx)(n.a,{href:"#code-solution-1","aria-hidden":"true",tabIndex:"-1",children:(0,e.jsx)(n.span,{className:"icon icon-link"})}),"Code Solution"]}),(0,e.jsxs)(h,{children:[(0,e.jsx)(t,{label:"Python",language:"python",code:`def productExceptSelf(self, nums: List[int]) -> List[int]: n = len(nums) result = [1] * n # Calculate the prefix products (products to the left of each element) prefix_product = 1 for i in range(n): result[i] *= prefix_product prefix_product *= nums[i] # Calculate the postfix products (products to the right of each element) and update the result postfix_product = 1 for i in range(n - 1, -1, -1): result[i] *= postfix_product postfix_product *= nums[i] return result`}),(0,e.jsx)(t,{label:"Javascript",language:"javascript",code:`var productExceptSelf = function(nums) { const n = nums.length; const result = new Array(n).fill(1); let prefixProduct = 1; for (let i = 0; i < n; i++) { result[i] *= prefixProduct; prefixProduct *= nums[i]; } let postfixProduct = 1; for (let i = n - 1; i >= 0; i--) { result[i] *= postfixProduct; postfixProduct *= nums[i]; } return result; };`}),(0,e.jsx)(t,{label:"Java",language:"javascript",code:`public int[] productExceptSelf(int[] nums) { int n = nums.length; int[] result = new int[n]; int prefixProduct = 1; for (int i = 0; i < n; i++) { result[i] = prefixProduct; prefixProduct *= nums[i]; } int postfixProduct = 1; for (int i = n - 1; i >= 0; i--) { result[i] *= postfixProduct; postfixProduct *= nums[i]; } return result; }`})]}),(0,e.jsx)(n.hr,{})]})]}),(0,e.jsxs)(o,{children:[(0,e.jsx)(c,{children:"Solution Q3"}),(0,e.jsxs)(l,{children:[(0,e.jsx)(n.p,{children:(0,e.jsx)(n.strong,{children:"Solution Overview:"})}),(0,e.jsxs)(n.ol,{children:[(0,e.jsxs)(n.li,{children:[(0,e.jsx)(n.strong,{children:"Create a hashmap (hm)"})," to store the frequency of each element in the input array."]}),(0,e.jsx)(n.li,{children:"Convert the hashmap items into pairs and store them in a list (pairs)."}),(0,e.jsxs)(n.li,{children:[(0,e.jsx)(n.strong,{children:"Sort the list of pairs"})," based on the frequency in descending order."]}),(0,e.jsx)(n.li,{children:"Extract the first k elements from the sorted list."})]}),(0,e.jsx)(n.p,{children:(0,e.jsx)(n.strong,{children:"Time Complexity:"})}),(0,e.jsx)(n.ul,{children:(0,e.jsxs)(n.li,{children:[(0,e.jsx)(n.code,{children:"O(N log N)"}),", where N is the length of the input array. This is due to the sorting step."]})}),(0,e.jsx)(n.p,{children:(0,e.jsx)(n.strong,{children:"Space Complexity:"})}),(0,e.jsx)(n.ul,{children:(0,e.jsxs)(n.li,{children:[(0,e.jsx)(n.code,{children:"O(N)"})," for the hashmap and O(N) for the list of pairs."]})}),(0,e.jsxs)(n.h4,{id:"code-solution-2",children:[(0,e.jsx)(n.a,{href:"#code-solution-2","aria-hidden":"true",tabIndex:"-1",children:(0,e.jsx)(n.span,{className:"icon icon-link"})}),"Code Solution"]}),(0,e.jsxs)(h,{children:[(0,e.jsx)(t,{label:"Python",language:"python",code:`def topKFrequent(self, nums: List[int], k: int) -> List[int]: hm = {} for n in nums: hm[n] = 1 + hm.get(n, 0) pairs = [] for key, value in hm.items(): pairs.append([key, value]) pairs.sort(key=lambda pair: pair[1], reverse=True) return [x[0] for x in pairs][:k]`}),(0,e.jsx)(t,{label:"JavaScript",language:"javascript",code:`var topKFrequent = function(nums, k) { let frequencyMap = new Map(); // Step 1: Create a hashmap to store the frequency of each element for (let num of nums) { frequencyMap.set(num, 1 + (frequencyMap.get(num) || 0)); } let pairs = Array.from(frequencyMap.entries()); // Step 2: Sort the pairs based on frequency in descending order pairs.sort((a, b) => b[1] - a[1]); // Step 3: Extract the k most frequent elements return pairs.slice(0, k).map(pair => pair[0]); }; `}),(0,e.jsx)(t,{label:"Java",language:"javascript",code:`public int[] topKFrequent(int[] nums, int k) { Map frequencyMap = new HashMap<>(); // Step 1: Create a hashmap to store the frequency of each element for (int num : nums) { frequencyMap.put(num, 1 + frequencyMap.getOrDefault(num, 0)); } List> pairs = new ArrayList<>(frequencyMap.entrySet()); // Step 2: Sort the pairs based on frequency in descending order pairs.sort((a, b) -> b.getValue() - a.getValue()); // Step 3: Extract the k most frequent elements List result = new ArrayList<>(); for (int i = 0; i < k && i < pairs.size(); i++) { result.add(pairs.get(i).getKey()); } // Convert List to int[] return result.stream().mapToInt(Integer::intValue).toArray(); }`})]}),(0,e.jsx)(n.hr,{})]})]})]})]})]})}}var E=z;function a(i,r){throw new Error("Expected "+(r?"component":"object")+" `"+i+"` to be defined: you likely forgot to import, pass, or provide it.")}return M;})(); ;return Component;

Theory

Coding

Filter by difficulty