Find the Nearest Smaller Element on Left Side in an Array – Understand the Challenge to Solve it Efficiently

The Nearest Smaller Element problem explained:

Given an array (that is a list) of integers, for each element find all the nearest element smaller on the left side of it.

The naive solution has time complexity O(n^2). Can you solve it in O(n)? Well, you need to have a Stack to do that.

The naive solution is for each element to check all the elements on the left of it, to find the first one which is smaller.

The worst case run time for that would be O(n^2). For an array of length n, it would take: 0 + 1 + 2 + 3 + … + (n-1) comparisons. = (n-1)*n/2 = O(n^2) comparisons.

But with a stack we can improve that.

Want to learn more about Stacks?

Automate Posting on Facebook in Python – Follow these 7 easy steps

Overview

After this these steps you will be able to automate the process of posting on Facebook by a Python script. In this example I will show how it is done on a Facebook brand page, Learn Python With Rune.

What you need.

  • A graph API token, which you by registering as a developer on facebook and creating an App there.
  • Make a simple Python program using the facebook library

Step 1: Registering as developer at Facebook

To register as a developer at Facebook you need to log in to developer.facebook.com

You press the Log In in the top right corner and log in with you Facebook credentials.

Step 2: Create an App

You need to create an App to get the graph API token.

Under My Apps you press Create App.

Press the Manage Pages, Ads or Groups.

You enter App Display Name, which will be the name that is used when posting from this App. Hence, chose a name that you like people to see in the post.

Fill out your email (probably it is automatically there) and press Create App ID.

Step 3: Create Graph API token

Under tools choose Graph API explorer

Ensure that the right Facebook App is chosen. Then under User or Page chose get Page Access Token.

It will prompt you to log in to your Facebook account and ask permission for sharing your page.

Agree with that.

Then you will get back to this screen.

Where you want to add pages_manage_posts, that will grant you access to create posts.

Then click Generate Access Token and you will be prompted to agree with the new access rights on your Facebook page.

Step 4: Prolong you graph API token

The graph API token is quite short lived, so you want to extend it.

Press the info at the graph API token.

Then press the Open in Access Token Tool.

Where you in the bottom will find Extend Access Token. Press that.

Step 6: Install facebook-sdk library

To make you life easy in Python, you need to install the facebook-sdk library.

pip install facebook-sdk

Step 7: The Python magic

You need to insert you Access Token in the code.

Also, insert the page ID you want. You can find your Page ID with this page.

import facebook
page_access_token = "" # Replace with you access token
graph = facebook.GraphAPI(page_access_token)
facebook_page_id = "" # insert you page ID here.
graph.put_object(facebook_page_id, "feed", message='test message')

That’s it. Enjoy.

Automate a Quotation Image for Twitter in Python in 5 Easy Steps

The challenge

You have a quote and an image.

    quote = "Mostly, when you see programmers, they aren’t doing anything.  One of the attractive things about programmers is that you cannot tell whether or not they are working simply by looking at them.  Very often they’re sitting there seemingly drinking coffee and gossiping, or just staring into space.  What the programmer is trying to do is get a handle on all the individual and unrelated ideas that are scampering around in his head."
    quote_by = "Charles M. Strauss"
len(quote) = 430

The quote is long (430 chars) and the picture might be too bright to write in white text. Also, it will take time to find the right font size.

Can you automate that getting a result that fits the Twitter recommended picture size?

Notice the following.

  • The picture is dimmed to make the white text easy readable.
  • The font size is automatically adjusted to fit the picture.
  • The picture is cropped to fit recommended Twitter size (1024 x 512).
  • There is added a logo by your choice.

If this is what you are looking for, then this will automate that.

Step 1: Find your background picture and quote

In this tutorial I will use the background image and quote given above. But you can change that to your needs.

If you chose a shorter quote the font size will adjust accordingly.

Example given here.

Notice that the following.

  • The font size of the “quoted by” (here Learn Python With Rune) is adjusted to not fill more that half of the picture width.
  • You can modify the margins as you like – say you want more space between the text and the logo.

Step 2: Install the PILLOW library

The what? Install the pillow library. You can find installation documentation in their docs.

Or just type

pip install pillow

The pillow library is the PIL fork, and PIL is the Python Imaging Library. Basically, you need it for processing images.

Step 3: Download a font you want to use

You can find various fonts in font.google.com.

For this purpose, I used the Balsamiq Sans font.

I have located the bold and the italic version in a font folder.

Step 4: The actual Python code

This is the fun part. The actual code.

from PIL import Image, ImageDraw, ImageFont, ImageEnhance
# picture setup - it is set up for Twitter recommendations
WIDTH = 1024
HEIGHT = 512
# the margin are set by my preferences
MARGIN = 50
MARGIN_TOP = 50
MARGIN_BOTTOM = 150
LOGO_MARGIN = 25
# font variables
FONT_SIZES = [110, 100, 90, 80, 75, 70, 65, 60, 55, 50, 45, 40, 35, 30, 25, 20]
FONT_QUOTE = 'font-text'
FONT_QUOTED_BY = 'font-quoted-by'
FONT_SIZE = 'font-size'
FONT_QUOTED_BY_SIZE = 'font-quoted-by-size'
# Font colors
WHITE = 'rgb(255, 255, 255)'
GREY = 'rgb(200, 200, 200)'
# output text
OUTPUT_QUOTE = 'quote'
OUTPUT_QUOTED_BY = 'quoted-by'
OUTPUT_LINES = 'lines'

def text_wrap_and_font_size(output, font_style, max_width, max_height):
    for font_size in FONT_SIZES:
        output[OUTPUT_LINES] = []
        font = ImageFont.truetype(font_style[FONT_QUOTE], size=font_size, encoding="unic")
        output[OUTPUT_QUOTE] = " ".join(output[OUTPUT_QUOTE].split())
        if font.getsize(output[OUTPUT_QUOTE])[0] <= max_width:
            output[OUTPUT_LINES].append(output[OUTPUT_QUOTE])
        else:
            words = output[OUTPUT_QUOTE].split()
            line = ""
            for word in words:
                if font.getsize(line + " " + word)[0] <= max_width:
                    line += " " + word
                else:
                    output[OUTPUT_LINES].append(line)
                    line = word
            output[OUTPUT_LINES].append(line)
        line_height = font.getsize('lp')[1]
        quoted_by_font_size = font_size
        quoted_by_font = ImageFont.truetype(font_style[FONT_QUOTED_BY], size=quoted_by_font_size, encoding="unic")
        while quoted_by_font.getsize(output[OUTPUT_QUOTED_BY])[0] > max_width//2:
            quoted_by_font_size -= 1
            quoted_by_font = ImageFont.truetype(font_style[FONT_QUOTED_BY], size=quoted_by_font_size, encoding="unic")
        if line_height*len(output[OUTPUT_LINES]) + quoted_by_font.getsize('lp')[1] < max_height:
            font_style[FONT_SIZE] = font_size
            font_style[FONT_QUOTED_BY_SIZE] = quoted_by_font_size
            return True
    # we didn't succeed find a font size that would match within the block of text
    return False

def draw_text(image, output, font_style):
    draw = ImageDraw.Draw(image)
    lines = output[OUTPUT_LINES]
    font = ImageFont.truetype(font_style[FONT_QUOTE], size=font_style[FONT_SIZE], encoding="unic")
    line_height = font.getsize('lp')[1]
    y = MARGIN_TOP
    for line in lines:
        x = (WIDTH - font.getsize(line)[0]) // 2
        draw.text((x, y), line, fill=WHITE, font=font)
        y = y + line_height
    quoted_by = output[OUTPUT_QUOTED_BY]
    quoted_by_font = ImageFont.truetype(font_style[FONT_QUOTED_BY], size=font_style[FONT_QUOTED_BY_SIZE], encoding="unic")
    # position the quoted_by in the far right, but within margin
    x = WIDTH - quoted_by_font.getsize(quoted_by)[0] - MARGIN
    draw.text((x, y), quoted_by, fill=GREY, font=quoted_by_font)
    return image

def generate_image_with_quote(input_image, quote, quote_by, font_style, output_image):
    image = Image.open(input_image)
    # darken the image to make output more visible
    enhancer = ImageEnhance.Brightness(image)
    image = enhancer.enhance(0.5)
    # resize the image to fit Twitter
    image = image.resize((WIDTH, HEIGHT))
    # set logo on image
    logo_im = Image.open("pics/logo.png")
    l_width, l_height = logo_im.size
    image.paste(logo_im, (WIDTH - l_width - LOGO_MARGIN, HEIGHT - l_height - LOGO_MARGIN), logo_im)
    output = {OUTPUT_QUOTE: quote, OUTPUT_QUOTED_BY: quote_by}
    # we should check if it returns true, but it is ignorred here
    text_wrap_and_font_size(output, font_style, WIDTH - 2*MARGIN, HEIGHT - MARGIN_TOP - MARGIN_BOTTOM)
    # now it is time to draw the quote on our image and save it
    image = draw_text(image, output, font_style)
    image.save(output_image)

def main():
    # setup input and output image
    input_image = "pics/background.jpg"
    output_image = "quote_of_the_day.png"
    # setup font type
    font_style = {FONT_QUOTE: "font/BalsamiqSans-Bold.ttf", FONT_QUOTED_BY: "font/BalsamiqSans-Italic.ttf"}
    quote = "Mostly, when you see programmers, they aren’t doing anything.  One of the attractive things about programmers is that you cannot tell whether or not they are working simply by looking at them.  Very often they’re sitting there seemingly drinking coffee and gossiping, or just staring into space.  What the programmer is trying to do is get a handle on all the individual and unrelated ideas that are scampering around in his head."
    # quote = "YOU ARE AWESOME!"
    quote_by = "Charles M. Strauss"
    # quote_by = "Learn Python With Rune"
    # generates the quote image
    generate_image_with_quote(input_image, quote, quote_by, font_style, output_image)

if __name__ == "__main__":
    main()

Notice that you can change the input and output image names and locations in the main() function. Also, there you can setup the font for the quote and the quoted-by.

Finally, and obviously, you can change the quote and quote-by in the main() function.