Find the Length of the Longest Common Prefix | LeetCode 3043 - Python

Indiziert: 2026-05-21

[00:00:00]Hello everyone. I'm Paul and this is problem 3043.

[00:00:03]Find the length of the longest common prefix. This is a medium problem that might become tricky if you don't know how to build and use a try. So, let's start.

[00:00:14]This is a nice description. You can read it if you want. But basically, we have to return the length of the longest common prefix among all pairs. We are given these two arrays. Here, the longest common prefix is given by these two integers. And more specifically, the longest common prefix is 100. The length of this longest common prefix is three.

[00:00:38]So, the result in this case is three.

[00:00:41]The naive solution is the following. We can say that the result is initially zero because we are looking for the longest common prefix. And now we can go through every possible pair in these two arrays. First, we take the pair 1 1000.

[00:00:55]Here, the longest common prefix is one.

[00:00:58]And the length of this longest common prefix is one. Given that one is greater than zero, we can replace this with one.

[00:01:06]Next, we can try the pair 10 1000. Here, the longest common prefix is 10. The length of this is two. And two is greater than one. So, the result now is two. Finally, we can take the pair 100 1000. Here, the longest common prefix is 100. And the length of this prefix is three. Given that three is greater than two, the result is three. Now, this works technically. But down here we have the constraints and we know that these two arrays can have lengths of up to 5 * 10 ^ 4. And if we iterate every possible pair, this requires roughly big O of n squared. It's actually a bit more because we are transforming every integer into a string. And this number to the power of two is a a large number which we can't handle. So, we have to think about something else. The key here is that we can use something called a trie. So, let's see how this works. This is the final trie if we decide to add every number in array one. So, let's see how to build this.

[00:02:14]Let's say that we are trying to add this number into the trie. We always start from the root, and for every node we have different amounts of children. We can have zero or more. In this case, we have zero.

[00:02:27]So, we are trying to add this. First, we check if we have this number as a child.

[00:02:33]Given that we don't, we add it.

[00:02:36]And that's it. Now, we have successfully inserted this number. Now, we can continue with this one. So, we start from the root every time, and we are going character by character, or in this case, digit by digit. We start from index zero, so first, the I pointer is here. We start with one. We are checking if from the root, we have a child that's equal to one, and we have it right here.

[00:03:01]So, now we are standing at this node, and we can move the I pointer one step to the right. Next, we are here, and the current digit is zero. So, we are checking if from this node, we have a child that's equal to zero. Given that we don't, we need to build a node with a value of zero.

[00:03:19]Now, we have successfully inserted this value, and we can continue with the final one. We start with the I pointer at the first digit. We start from the root in the trie, and we are checking if we have a one as a child. Given that we do, we can continue. Now, the I pointer is here, and we are checking if from this point, we have zero as a child. And we do have zero, so we continue. Now, the I pointer is here, and from here, we don't have another zero as a child, so we add it.

[00:03:49]And now that we have this, we can go through every value in array two and check what's the longest common prefix.

[00:03:57]So, we can say that the result is initially zero and here we only have one element. So, we are doing something very similar. We go digit by digit starting from index zero and we will keep track of the current common prefix with a value which we'll call count. This is initially zero. And we always start from the root. So, we are checking if from this node we have a child that's equal to one and we do have one. So, we can increase one here. The count is one.

[00:04:28]And we can continue with the next index.

[00:04:32]Now we need a zero and from this node we have zero as a child, so we add one to the count. This is two and we move the I pointer.

[00:04:41]Now the I pointer is here. So, from this node we are checking if we have zero as a child and we do have zero. So, we add one to the count and move the I pointer.

[00:04:51]Finally, the I pointer is here and we are standing at this node. Given that we don't have zero as a child, we can break the loop now and the maximum common prefix so far is three. Given that we only have one value here, that's it. The result is the maximum between zero and three, which is three. So, we return this.

[00:05:12]And by doing this, we are solving the problem in roughly big O of M plus M.

[00:05:17]Why? Well, because first we need to add all these values into the trie. Remember that for each number, we are going through every digit one by one and at the same time we are iterating these nodes. So, overall time complexity for inserting each value is roughly big O of one because the numbers are relatively small. So, overall time complexity for inserting the values in array one is roughly big O of N. And then we have to go through the values in array two to check what's the longest common prefix.

[00:05:50]So, this is overall time complexity and overall space complexity is roughly big O of N because remember that we start by adding these values into the tri. So, the space is given by this.

[00:06:05]In the worst case, we have no shared prefixes. For example, we can have 3 5 7 and so on. Every prefix is different and in this case overall space is big O of N. So, with this in mind, now let's go with the code. First, we need to build two classes for the tri. We will call the first one tri node.

[00:06:29]So, here we need a constructor. In Python, we use init and this takes self and some value. We will say that this is an empty string by default. Now, here we will say that self. children is an empty map and self.value is the value that we are giving here.

[00:06:52]Now, we can build another class for the tri.

[00:06:56]This requires another constructor. So, here we use init again and this takes self.

[00:07:03]Here we will say that self.root is equal to a new tri node.

[00:07:09]Now, we need two methods. We will call the first one insert. This takes self and some value. This is how we add numbers.

[00:07:19]And here we say that current is equal to self.root.

[00:07:23]And we can say for every character in the value, if we don't have the character in current.children, sorry, this is children.

[00:07:36]This means that we need to build the new node. So, current.children at C is now equal to a new trie node using C as the value.

[00:07:48]And every time we need to move to the next node. Remember the drawing. So, we say that current is equal to current dot children at C. And that's it for insert.

[00:08:00]Now, we can move to the next method, which is max prefix. So, this takes self and some value.

[00:08:09]Remember that we are using this for array two.

[00:08:13]Here, we do something very similar.

[00:08:14]Current is equal to self dot root.

[00:08:17]We can say that count, sorry, count is equal to zero.

[00:08:22]And for every character in the value that we are given, if we don't have this character in current dot children, we can break the loop right away and return count. Else, if we are here, we can say that current is equal to current dot children at C.

[00:08:46]And we add one to the count.

[00:08:49]After all of this, we can just return count. Sorry.

[00:08:54]out.

[00:08:55]Okay?

[00:08:57]And now with the trie, we can say that N is the length of array one. M is the length of array two.

[00:09:06]The result is initially zero. And finally, we want to return this result.

[00:09:11]Here in between, we can build an instance of the trie. So, we do this. And now, we can first add the values from array one and then find the longest common prefix. So, we say for every value in array one, trie dot insert. And here, we need to take the current value in string format.

[00:09:35]Because remember that we have to go through a ready sheet. So, we transform the number into a string like this in Python.

[00:09:43]And now we can move to the next part, which is find the longest common prefix. We say for every value in array two, the result is the maximum between what we already have in the result and try.max_prefix.

[00:10:01]And here we take the value in string format.

[00:10:05]Okay?

[00:10:06]So, this is the entire code.

[00:10:08]Let's submit this and see if it works.

[00:10:11]As you can see, this works and it's very efficient. This is relatively simple to explain, but might be slightly harder to code. So, in case you didn't get the idea, I highly recommend you to watch this video again from the start. If you found this useful, please drop a like, subscribe, and see you in the next one.

[00:10:30]Bye-bye.