Need the second smallest and second largest in one array? We compare a clear two-pass \u201cbetter\u201d method with a one-pass optimal trick. Full intuition, commented code, dry runs, and Big-O analysis.<\/p>\n\n\n\n
So let’s get started with the [Problem Link<\/span><\/mark><\/a><\/strong>].<\/p>\n\n\n You are given an array All elements are distinct, and We need the top two<\/strong> and bottom two<\/strong> distinct numbers.1. Problem statement<\/h2>\n\n\n\n
\n
a<\/code> of length n<\/code>.
Return a list [secondLargest, secondSmallest]<\/code>, where<\/p>\n\n\n\n\n
secondLargest<\/code> = the second-largest distinct value in a<\/code><\/li>\n\n\n\nsecondSmallest<\/code> = the second-smallest distinct value in a<\/code><\/li>\n<\/ul>\n\n\n\nn \u2265 2<\/code>.<\/p>\n<\/blockquote>\n\n\n\n
\n\n\n\n2. Example<\/h2>\n\n\n\n
a<\/code><\/th>Answer<\/th> Why<\/th><\/tr><\/thead> [5, 1, 3, 4, 2]<\/code><\/td>[4, 2]<\/code><\/td>Sorted order \u2192 1 < 2 < 3 < 4 < 5<\/code>.
Second-largest = 4, second-smallest = 2<\/td><\/tr>[9, 7]<\/code><\/td>[7, 9]<\/code><\/td>Only two values: second-largest = smaller one (7), second-smallest = larger one (9).<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
\n\n\n\n3. High-level idea<\/h2>\n\n\n\n
No sorting is required; a couple of variables can track them while we scan the array.<\/p>\n\n\n\n\n