ArrayList vs HashMap time complexity

Question

The scenario is the following:

You have 2 strings (s1, s2) and want to check whether one is a permutation of the other so you generate all permutations of lets say s1 and store them and then iterate over and compare against s2 until either it's found or not.

Now, in this scenario, i am deliberating whether an ArrayList is better to use or a HashMap when considering strictly time complexity as i believe both have O(N) space complexity.

According to the javadocs, ArrayList has a search complexity of O(N) whereas HashMap is O(1). If this is the case, is there any reason to favor using ArrayList over HashMap here since HashMap would be faster?

The only potential downside i could think of is that your (k,v) pairs might be a bit weird if you did something like where the key = value, i.e. {k = "ABCD", v = "ABCD"}, etc..

@chrylis-cautiouslyoptimistic- Because it's the algorithm i came up with. — Javia1492
– Javia1492, Commented Jan 12, 2021 at 5:01
Generating the permutations is extremely expensive, not to mention the time and space complexity to do so. There is another way to perform the check that is much cheaper. It does involve reordering the strings. — chrylis -cautiouslyoptimistic-
– chrylis -cautiouslyoptimistic-, Commented Jan 12, 2021 at 5:03
Generating all permutations is O(n!), which is really bad. It's even worse than exponential. To get an idea of how bad O(n!) is, imagine you tried to sort a deck of cards by shuffling it over and over until all the cards randomly ended up in order. That algorithm would also be O(n!). — John Kugelman
– John Kugelman, Commented Jan 12, 2021 at 5:17
You need to come up with a better algorithm. Think about it. — Stephen C
– Stephen C, Commented Jan 13, 2021 at 2:17

Mick · Accepted Answer · 2021-01-13 02:14:06Z

As shown here:

import java.io.*; 
import java.util.*; 
  
class GFG{ 
      
    static int NO_OF_CHARS = 256; 
      
    /* function to check whether two strings 
    are Permutation of each other */
    static boolean arePermutation(char str1[], char str2[]) 
    { 
        // Create 2 count arrays and initialize 
        // all values as 0 
        int count1[] = new int [NO_OF_CHARS]; 
        Arrays.fill(count1, 0); 
        int count2[] = new int [NO_OF_CHARS]; 
        Arrays.fill(count2, 0); 
        int i; 
   
        // For each character in input strings, 
        // increment count in the corresponding 
        // count array 
        for (i = 0; i <str1.length && i < str2.length ; 
                                                 i++) 
        { 
            count1[str1[i]]++; 
            count2[str2[i]]++; 
        } 
   
        // If both strings are of different length. 
        // Removing this condition will make the program  
        // fail for strings like "aaca" and "aca" 
        if (str1.length != str2.length) 
            return false; 
   
        // Compare count arrays 
        for (i = 0; i < NO_OF_CHARS; i++) 
            if (count1[i] != count2[i]) 
                return false; 
   
        return true; 
    } 
   
    /* Driver program to test to print printDups*/
    public static void main(String args[]) 
    { 
        char str1[] = ("geeksforgeeks").toCharArray(); 
        char str2[] = ("forgeeksgeeks").toCharArray(); 
          
        if ( arePermutation(str1, str2) ) 
            System.out.println("Yes"); 
        else
            System.out.println("No"); 
    } 
} 
  
// This code is contributed by Nikita Tiwari.

If you're glued to your implementation, use a HashSet, it still has O(1) lookup time, just without keys

Karanjot Singh · Accepted Answer · 2021-01-14 20:11:57Z

0

You can use HashSet as you need only one parameter.

answered Jan 14, 2021 at 20:11

Karanjot Singh

1567 bronze badges

Collectives™ on Stack Overflow

ArrayList vs HashMap time complexity

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related