Magic Array Index Time/Space Complexity

magic index leetcode
find a fixed point (value equal to index) in a given array
find a fixed point (value equal to index) in a given array | duplicates allowed
geeksforgeeks magic index
algorithm to find element in array
array index and element equality java
magic index ctci
fixed point leetcode

I've been looking at the following problem:

Magic Index: A magic index in an array A[0...n-1] is defined to be an index i such as A[i] = i. Given a sorted non-distinct array of integers, write a method to find a magic index if one exists.

Here is my solution:

static int magicNonDistinct(int[] array, int start, int end) {
  if (end < start) return -1;
  int mid = start + (end - start) / 2;
  if (mid < 0 || mid >= array.length) return -1;

  int v = array[mid];
  if (v == mid) return mid;

  int leftEnd = Math.min(v, mid - 1);
  int leftRes = magicNonDistinct(array, start, leftEnd);
  if (leftRes != -1) return leftRes;

  int rightStart = Math.max(v, mid + 1);
  int rightRes = magicNonDistinct(array, rightStart, end);
  return rightRes;
}

It works just fine and is the recommended solution from the book Cracking The Code Interview 6th Edition, problem 8.3 Follow up (sorry for spoiling).

However when running this on a distinct array with no magic index, it visits all the elements, yielding a worst case running time of O(n).

Since it is recursive it takes O(n) memory as worst case.

Why would this solution be preferable to just iterating over the array? This solution (my own) is better I would argue:

static int magicNonDistinctV2(int[] array) {
  for (int i = 0; i < array.length; ++i) {
    int v = array[i];
    if (v == i) return v;
    if (v >= array.length) return -1;
    else if (v > i) i = v - 1;
  }

  return -1;
}

O(n) running time O(1) space always?

Could somebody derive a better time complexity for the initial algorithm? I've been thinking about looking if it is O(d), where d is the number of distinct elements, however that case is also wrong since the min/max only works in one direction (think about if v = 5, mid = 4 and the lower part of the array is all fives).

EDIT:

Ok people think I'm bananas and scream O(log(n)) as soon as they see something that looks like binary search. Sorry for being unclear folks.

Let's talk about the code in the first posting I made (the solution by CTCI):

If we have an array looking like this: [-1, 0, 1, 2, 3, 4, 5, 6, 7, 8], actually an array looking like this: [-1,...,n-2] of size n, we know that there is not element that can match. However - the algorithm will visit all elements since the elements aren't unique. I dare you, run it, it can not divide the search space by 2 as in a regular binary search. Please tell me what is wrong with my reasoning.

No, in my opinion the first solution is not O(log n) as other answers state, it is really O(n) worst case (in the worst case it still needs to go through all the elements, consider equivalence array shifted by one as also mentioned by the author).

The cause why it is not O(log n) is because it needs to search on both sides of the middle (binary search only checks one side of middle therefore it is O(log n)).

It allows to skip items if you're lucky, however your second iterative solution skips items too if not needed to look on them (because you know there cannot be magic index in such range as the array is sorted) so in my opinion the second solution is better (the same complexity + iterative i.e. better space complexity and no recursive calls which are relatively expensive).

EDIT: However when I thought about the first solution again, it on the other side allows to also "skip backwards" if possible, which the iterative solution does not allow - consider for example an array like { -10, -9, -8, -7, -6, -5 } - the iterative solution would need to check all the elements, because it starts at the beginning and the values do not allow to skip forward, whereas when starting from the middle, the algo can completely skip checking the first half, then the first half of the second half, etc.

Magic Array Index Time/Space Complexity - arrays - php, However when running this on a distinct array with no magic index, it visits all the elements, yielding a worst case running time of O(n). Since it is recursive it  Index i of A is said to be connected to index j if j = (i + A[i]) % n + 1 (Assume 1-based indexing). Start traversing array from index i and jump to its next connected index. If on traversing array in the described order, index i is again visited then index i is a magical index. Count the number of magical indexes in the array.

Magical Indices in an array, Count the number of magical indexes in the array. This property will be helpful in reducing the time complexity of the solution. Space Complexity: O(n). Magic Index – Find Index In Sorted Array Such That A[i] = i. Objective: Given a sorted array of distinct integers, Find the Magic index or Fixed point in the array. Magic Index or Fixed Point: Magic index or a Fixed point in an array is an index i in the array such that A[i] = i.

It looks like you misunderstood the time complexity the required solution. The worse case is not O(n), it is O(log(n)). This is because during each pass you search next time only half of the array.

Here is a C++ example and check that for the whole array of 11 elements, it take only 3 checks.

Magic Index, Given a sorted array of integers, Find the Magic index or Fixed point in the array. Better solution would Modify the Binary Search – Time Complexity O(logN). For arrays containing 10 or fewer elements, time complexity of.sort is O(n^2), and space complexity is O(1). For longer arrays time complexity is Θ(n log(n)) (average case), and space complexity is O(log(n))

Search Algorithms in Java, There shouldn't be a difference regarding time and space complexity between The compiled array stores the index position of previous occurrence of the Let's take a look at how the interpolation formulae works its magic to look for 6 : We could optimize the space complexity by taking dp[i-1] which is the previous sum into a variable, eliminating the need for dp[] array. Time Complexity: O(N) Space Complexity: O(1) We could also find the indices of the subarray having the maximum sum.

Given an array of integers where each element points to , index of the next element how would you detect if there is a cycle in this array? Tags: What as the time and space complexity of the best solution? Can you do​  Know Thy Complexities! Hi there! This webpage covers the space and time Big-O complexities of common algorithms used in Computer Science. When preparing for technical interviews in the past, I found myself spending hours crawling the internet putting together the best, average, and worst case complexities for search and sorting algorithms so that I wouldn't be stumped when asked about them.

JS objects and arrays, Objects and arrays are 2 basic data structures in JavaScript and both offer Look up, Assign value: O(1) constant time complexity because there is no item MAGIC! — It returns only numbers within the bound of the available indices (so it to the same location…. it will be O(n) to loop through existing stored values!) Solution. From the looks of it, this seems like a simple enough problem to solve in linear time and space. We can simply take the product of all the elements in the given array and then, for each of the elements of the array, we can simply find product of array except self value by dividing the product by .

Comments
  • Thanks for understanding the question, however can you derive another time complexity, e.g. introducing a distinct variable d or something? If nobody else answers something more in-depth, I'll accept your answer.
  • I'll just call it for now, however thank you for your breakdown of the problem. You got an upvote!
  • @JohanS: I broke-down the problem to highlight the fact that when the reason to not visit the array-halves are missing, you will eventually end up visiting the entire array. Otw, as you said, people conclude Log(n) when they see something that looks like binary search.
  • If you look at this example: [-1, 0, 1, 2, 3, 4, 5, 6, 7, 8], it will visit all elements, since we are not searching for a criterion which can be caught with a regular binary search (hence, we can't divide in two).
  • By the way, your algorithm is for distinct values, doesn't work with non-distinct values, try this one: [5, 5, 5, 5, 5, 5, 1337].