LeetCode: Lexicographical Numbers (DFS, math, tree pruning)
https://leetcode.com/problems/lexicographical-numbers/, problem statement:
Not the most efficient solution (possibly because of the stack overhead), but passable in O(n)-time. Code's below. Cheers, Marcelo
public class Solution
{
public IList<int> LexicalOrder(int n)
{
List<int> retVal = new List<int>();
LexicalOrderInternal(1, 10, n, retVal);
return retVal;
}
private void LexicalOrderInternal(int init, int end, int n, List<int> retVal)
{
for (int i = init; i < end; i++)
{
if (i > n) return;
retVal.Add(i);
if (10 * i <= n) LexicalOrderInternal(10 * i, 10 * i + 10, n, retVal); //Tree pruning here!
}
}
}
Given an integer n, return 1 - n in lexicographical order.
For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9].
Please optimize your algorithm to use less time and space. The input size may be as large as 5,000,000.
Definitely the solution must be at least O(n) to work, anything higher than that and we'll have a problem given the 5M ceiling for the input size. I tried a couple of ideas to come up with the proper lexicographic order. One possible hypothesis was:As you try number "i", see if the number 10*i also works. If so it should come next after "i" instead of i+1Also, when calling recursively for 10*i, make sure you only go up to 10*i+10, after that point you'll be repeating numbers (and in non-lexicographic order), hence stop there.
Not the most efficient solution (possibly because of the stack overhead), but passable in O(n)-time. Code's below. Cheers, Marcelo
{
public IList<int> LexicalOrder(int n)
{
List<int> retVal = new List<int>();
LexicalOrderInternal(1, 10, n, retVal);
return retVal;
}
private void LexicalOrderInternal(int init, int end, int n, List<int> retVal)
{
for (int i = init; i < end; i++)
{
if (i > n) return;
retVal.Add(i);
if (10 * i <= n) LexicalOrderInternal(10 * i, 10 * i + 10, n, retVal); //Tree pruning here!
}
}
}
Very nice! My solution contains a bit of duplication I didn't bother to remove (yes, I'm very lazy), but, hey, it beats 100% of other submissions with 168ms to run :)
ReplyDeleteclass Solution {
private:
void explore(int k, int n, vector &result) {
if (k > n) return;
result.push_back(k);
for (int i = 0; i <= 9; ++i) {
int next = k * 10 + i;
if (next > n) break;
explore(next, n, result);
}
}
public:
vector lexicalOrder(int n) {
vector result; result.reserve(n);
for (int i = 1; i <= min(n, 9); ++i) explore(i, n, result);
return result;
}
};
You can improve your solution's speed by creating a list of a required size, since you know that there will be n elements stored in it.