When Gates and Allen launched Microsoft they thought they were too late, that there were too many other established companies in the market to be able to find a niche for themselves. When google launched web search was half a decade old and dozens of companies were in the market. When apple launched the ipod mp3 players had already been around for years and gone through many generations.
An absence of competition is a near certain way to gain market share, but the easy way is not the only way. If you have a good enough product you can steal business from the competion and even grow the size of the total market (as was the case with the ipod and iphone).