The size of your input is obviously O(n), but the memory requirements of this function is O(1), since the array has constant size. The time complexity is O(n) though, since it iterates over the string..
how space complexity of this code is O(n)?
-
27-06-2022 - |
Frage
public static boolean isUniqueChars2(String str) {
boolean[] char_set = new boolean[256];
for (int i = 0; i < str.length(); i++) {
int val = str.charAt(i);
if (char_set[val])
return false;
char_set[val] = true;
}
return true;
}
Lösung
Andere Tipps
Not counting the input string, the code has O(1)
space complexity. It consumes a constant amount of space irrespective of the input.
The time complexity is also O(1)
, since the loop will never execute more than 256 steps.
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow