Talk with You Series #1

**cover image mirrors mood at the moment of posting

Wanna start with the thoughts, that for a while, I do have a habit to write down challenges and their potential solutions I used to face on a daily basis, whether it was part of my job or free time activities.

Starting from this post, I've decided to introduce "Talk with You" series, where I'd post them in here (at least for now, at most once in few days) to spot them out to the public.

On one hand now I'll glimpse in here from time to time instead of my well structured notes to revamp some information and DevCommunity gonna handle storage, navigation in ascending order and all the other stuff, on another one I believe the things I write here might find the audience not on my behalf only. Fasten, let's kick off.

Count Occurrences

Quite often working with DS u need to count an amount of occurrences of values and afterwords to query those in an efficient manner, preferably Time O(1).

Obviously, you might think of creating HashTable and then traverse DS, populating the HashTable. That's true and might look as:

iterable = [...]
hashtable = {}
for value in iterable:
    hashtable[value] = hashtable.get(value, 0) + 1

Today I faced an alternative approach which would perfectly work on lists of digits avoiding usage of HashTable (sometimes it might be a necessity).

The idea behind is firstly to get the maximum value from list and create a new list of length of the maximum value, which will be used as indices mapping.

list_ = [1, 1, 2, 3]
max_ = max(list_)
indices = [0] * max_   # [0, 0, 0, 0]

Now, lets' traverse original list and map occurrence of each value in indices list.

1. iteration
[1, 1, 2, 3] # list
 |

[0, 1, 0, 0] # indices

2. iteration
[1, 1, 2, 3] # list
    |

[0, 2, 0, 0] # indices

3. iteration
[1, 1, 2, 3] # list
       |

[0, 2, 1, 0] # indices

4. iteration
[1, 1, 2, 3] # list
          |

[0, 2, 1, 1] # indices

What just happened. Well, basically, we took value from original list and used it as index in our indices list (and incremented value at index).

Now if we would like to represent our results using mapping list, we might say, there are 0 zero-s because at index 0 we have value 0, at index 1 we do have value of 2, meaning there are 2 one-s, at index 2 we have value of 1, meaning there are 1 two-s, etc.

Mirror Elements in Matrix

Even though holding 2 degrees BSc and MSc, when I find out a new math trick, I'm still getting the feelings of fascinating, aka "gosh, that's so simple and works".

Okay, back to the topic, assume you have a matrix of N*N and you need to reverse rows and columns in way to get the maximum sum of all the elements (row by row).

matrix 4*4

1 2 3 9
0 9 8 2
5 1 7 4
8 2 6 7  

From the first glimpse, perhaps you even do not know where to start from. But here is the trick with mirrored elements.

matrix 4*4

A B B A
C D D C
C D D C 
A B B A

The key point in here is, A in the matrix might be swapped only by another A-s. Lets image we are in the top left corner A (which is 1) and we'd like to know if there are another A (only mirrored A) which is grater. And indeed, we do have such in right upper corner (9).

Following the logic and recalling the original problem (max sum reversing rows and columns) we might conclude that in reality we do not need to perform any reverse operations, instead just look up the max value among mirrored ones. And that's it.

Stack. Trade-off between Time and Space complexity.

Assume you've got a task to implement a stack wrapper with only 3 functionalities: (1) pop (2) push (3) get_min. You might use interface of stack for (1) pop and (2) push, however still need to implement (3) get_min. Annnd get_min() should work for O(1) Time.

Well, when I's firstly tackling the problem, I completely forgot about a trade-off, which says: "When you optimise Time performance, you probably get worse with Space and wise versa". Why it's important, cause I started thinking of optimised DS which lead me to HashTables, but I truly missed naive lists, which could work for O(1) (amortised) as well.

So I reached the point when I was creating a HashTable where I might store each state of a wrapper class ... will stop here cause "simpler is a better option" (sometimes). Let's see the implementation with additional list to store min value for every state of stack.

class Wrapper:
   def __init__(self, stack):
      self.stack = stack
      self.min = []

   # Time O(1)
   def pop(self):
      self.stack.pop()
      self.min.pop()

   # Time O(1)
   def push(self, value):
      self.stack.push(value=value)
      min_ = self.min[-1]
      if value < min_:
          min_ = value
      self.min.append(min_)

   # Time O(1)
   def get_min(self):
      return self.min[-1]

As simple as it is.

Concluding

• keep coding and developing
• remember about trade-offs and do not overcomplicate (when u are not asked)

The above is the detailed content of Talk with You Series #1. For more information, please follow other related articles on the PHP Chinese website!