KnowledgeHub
Questions
Tags
Users
Search
Alex Rivera
|
Logout
Edit Question
Title
Body
Given an array of int, each int appears exactly TWICE in the array. find and return the int such that this pair of int has the max distance between each other in this array. e.g. [2, 1, 1, 3, 2, 3] 2: d = 5-1 = 4; 1: d = 3-2 = 1; 3: d = 6-4 = 2; return 2 My ideas: Use hashmap, key is the a[i] , and value is the index. Scan the a[] , put each number into hash. If a number is hit twice, use its index minus the old numbers index and use the result to update the element value in hash. After that, scan hash and return the key with largest element (distance). it is O(n) in time and space. How to do it in O(n) time and O(1) space ?
Tags (comma-separated)
Save Edits
Cancel